C++ Program to Check whether Graph is a Bipartite using 2 Color Algorithm

«
»
This C++ Program checks whether Graph is a Bipartite using 2 Color Algorithm

Here is source code of the C++ Program to check whether Graph is a Bipartite using 2 Color Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Check whether Graph is a Bipartite using 2 Color Algorithm
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #define V 4
  7. using namespace std;
  8. /* 
  9.  * A utility function to check if the current color assignment
  10.  * is safe for vertex v  
  11.  */
  12. bool isSafe (int v, bool graph[V][V], int color[], int c)
  13. {
  14.     for (int i = 0; i < V; i++)
  15.         if (graph[v][i] && c == color[i])
  16.             return false;
  17.     return true;
  18. }
  19.  
  20. /* 
  21.  * A recursive utility function to solve m coloring problem 
  22.  */
  23. bool graphColoringUtil(bool graph[V][V], int m, int color[], int v)
  24. {
  25.     if (v == V)
  26.         return true;
  27.     for (int c = 1; c <= m; c++)
  28.     {
  29.         if (isSafe(v, graph, color, c))
  30.         {
  31.             color[v] = c;
  32.             if (graphColoringUtil (graph, m, color, v+1) == true)
  33.                 return true;
  34.            color[v] = 0;
  35.         }
  36.     }
  37.     return false;
  38. }
  39.  
  40. /* 
  41.  * This function solves the m Coloring problem using Backtracking.
  42.  */
  43. bool graphColoring(bool graph[V][V], int m)
  44. {
  45.     int *color = new int[V];
  46.     for (int i = 0; i < V; i++)
  47.        color[i] = 0;
  48.     if (graphColoringUtil(graph, m, color, 0) == false)
  49.         return false;
  50.     return true;
  51. }
  52.  
  53. /* 
  54.  * Main Contains Menu 
  55. */
  56. int main()
  57. {
  58.     bool graph[V][V] = {{0, 1, 1, 1},
  59.         {1, 0, 1, 0},
  60.         {1, 1, 0, 1},
  61.         {1, 0, 1, 0},
  62.     };
  63.     bool gr[V][V] = {{0, 1, 0, 1},
  64.         {1, 0, 1, 0},
  65.         {0, 1, 0, 1},
  66.         {1, 0, 1, 0}
  67.     };
  68.     int m = 2;
  69.     if (graphColoring (graph, m))
  70.         cout<<"The graph 1 is Bipartite"<<endl;
  71.     else
  72.         cout<<"The graph 1 is not Bipartite"<<endl;
  73.     if (graphColoring (gr, m))
  74.         cout<<"The graph 2 is Bipartite"<<endl;
  75.     else
  76.         cout<<"The graph 2 is not Bipartite"<<endl;
  77.     return 0;
  78. }

advertisement
$ g++ bipartite_2color.cpp
$ a.out
The graph 1 is not Bipartite
The graph 2 is Bipartite
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn