C++ Program to Check whether a Graph is 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. }

$ 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
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.