C++ Program to Check whether Graph is a Bipartite using DFS

«
»
This C++ Program checks whether Graph is a Bipartite using DFS

Here is source code of the C++ Program to check whether Graph is a Bipartite using DFS. 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 DFS
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <stack>
  7. #include <list>
  8. using namespace std;
  9. /*
  10.  * Class Declaration
  11.  */
  12. class Graph
  13. {
  14.     public:
  15.         int V;
  16.         list<int> *adj;
  17.         Graph(int V);
  18.         void addEdge(int v, int w);
  19. };
  20. /*
  21.  * Constructor
  22.  */
  23. Graph::Graph(int V)
  24. {
  25.     this->V = V;
  26.     adj = new list<int>[V];
  27. }
  28. /*
  29.  * Adding Edge to Graph
  30.  */
  31. void Graph::addEdge(int v, int w)
  32. {
  33.     adj[v].push_back(w);
  34.     adj[w].push_back(v);
  35. }
  36. /*
  37.  * Class Bipartite Declaration
  38.  */
  39. class Bipartite
  40. {
  41.     private:
  42.         bool isBipartite;
  43.         bool *color;
  44.         bool *marked;
  45.         int *edgeTo;
  46.         stack<int> cycle;
  47.     public:
  48.         Bipartite(Graph G)
  49.         {
  50.             isBipartite = true;
  51.             color = new bool [G.V];
  52.             marked = new bool [G.V];
  53.             edgeTo = new int [G.V];
  54.             for (int v = 0; v < G.V; v++)
  55.             {
  56.                 if (!marked[v])
  57.                 {
  58.                     color[v] = false;
  59.                     dfs(G, v);
  60.                 }
  61.             }
  62.         }
  63.         /*
  64.          * DFS
  65.          */
  66.         void dfs(Graph G, int v)
  67.         {
  68.             marked[v] = true;
  69.             list<int>::iterator w;
  70.             for (w = G.adj[v].begin(); w != G.adj[v].end(); w++)
  71.             {
  72.                 if (!cycle.empty())
  73.                     return;
  74.                 if (!marked[*w])
  75.                 {
  76.                     edgeTo[*w] = v;
  77.                     color[*w] = !color[v];
  78.                     dfs(G, *w);
  79.                 }
  80.                 else if (color[*w] == color[v])
  81.                 {
  82.                     isBipartite = false;
  83.                     cycle.push(*w);
  84.                     for (int x = v; x != *w; x = edgeTo[x])
  85.                     {
  86.                         cycle.push(x);
  87.                     }
  88.                     cycle.push(*w);
  89.                 }
  90.             }
  91.         }
  92.         /* 
  93.          * Returns true if graph is Bipartite
  94.          */
  95.         bool isBi()
  96.         {
  97.             return isBipartite;
  98.         }
  99. };
  100.  
  101. /*
  102.  * Main Contains Menu
  103.  */
  104. int main()
  105. {
  106.     Graph g1(4);
  107.     g1.addEdge(0, 1);
  108.     g1.addEdge(0, 3);
  109.     g1.addEdge(1, 0);
  110.     g1.addEdge(1, 2);
  111.     g1.addEdge(2, 1);
  112.     g1.addEdge(2, 3);
  113.     g1.addEdge(3, 2);
  114.     g1.addEdge(3, 0);
  115.     Bipartite b(g1);
  116.     if (b.isBi())
  117.         cout<<"The graph is Bipartite"<<endl;
  118.     else
  119.         cout<<"The graph is not Bipartite"<<endl;
  120. }

advertisement
$ g++ bipartite_dfs.cpp
$ a.out
The graph 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