C++ Program to Check whether Graph is Biconnected

«
»
This C++ Program checks whether Graph is Biconnected.

Here is source code of the C++ Program to check whether Graph is Biconnected. 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 Biconnected
  3.  */
  4. #include <iostream>
  5. #include <list>
  6. #define NIL -1
  7. using namespace std;
  8.  
  9. /*
  10.  * Class Declaration
  11.  */
  12. class Graph
  13. {
  14.     private:
  15.         int V;
  16.         list<int> *adj;
  17.         bool isBCUtil(int v, bool visited[], int disc[], int low[],int parent[]);
  18.     public:
  19.         Graph(int V)
  20.         {
  21.             this->V = V;
  22.             adj = new list<int>[V]; 
  23.         }
  24.         void addEdge(int v, int w);
  25.         bool isBC();
  26. };
  27.  
  28. /*
  29.  * Add Edge to connect v and w
  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. /*
  38.  *  A recursive function that returns true if there is an articulation
  39.  *  point in given graph, otherwise returns false
  40.  */
  41. bool Graph::isBCUtil(int u, bool visited[], int disc[],int low[],int parent[])
  42. {
  43.  
  44.     static int time = 0;
  45.     int children = 0;
  46.     visited[u] = true;
  47.     disc[u] = low[u] = ++time;
  48.     list<int>::iterator i;
  49.     for (i = adj[u].begin(); i != adj[u].end(); ++i)
  50.     {
  51.         int v = *i;
  52.         if (!visited[v])
  53.         {
  54.             children++;
  55.             parent[v] = u;
  56.             if (isBCUtil(v, visited, disc, low, parent))
  57.                 return true;
  58.             low[u]  = min(low[u], low[v]);
  59.             if (parent[u] == NIL && children > 1)
  60.                 return true;
  61.             if (parent[u] != NIL && low[v] >= disc[u])
  62.                 return true;
  63.         }
  64.  
  65.         else if (v != parent[u])
  66.             low[u]  = min(low[u], disc[v]);
  67.     }
  68.     return false;
  69. }
  70.  
  71. /*
  72.  * returns true if graph is Biconnected, otherwise false.
  73.  */
  74. bool Graph::isBC()
  75. {
  76.     bool *visited = new bool[V];
  77.     int *disc = new int[V];
  78.     int *low = new int[V];
  79.     int *parent = new int[V];
  80.  
  81.     for (int i = 0; i < V; i++)
  82.     {
  83.         parent[i] = NIL;
  84.         visited[i] = false;
  85.     }
  86.  
  87.     if (isBCUtil(0, visited, disc, low, parent) == true)
  88.         return false;
  89.  
  90.     for (int i = 0; i < V; i++)
  91.         if (visited[i] == false)
  92.             return false;
  93.  
  94.     return true;
  95. }
  96.  
  97. /*
  98.  * Main Contains Menu
  99.  */
  100. int main()
  101. {
  102.     Graph g1(2);
  103.     g1.addEdge(0, 1);
  104.     if (g1.isBC())
  105.         cout<<"The Graph is BiConnected"<<endl;
  106.     else
  107.         cout<<"The Graph is not BiConnected"<<endl;
  108.  
  109.     Graph g2(5);
  110.     g2.addEdge(1, 0);
  111.     g2.addEdge(0, 2);
  112.     g2.addEdge(2, 1);
  113.     g2.addEdge(0, 3);
  114.     g2.addEdge(3, 4);
  115.     g2.addEdge(2, 4);
  116.     if (g2.isBC())
  117.         cout<<"The Graph is BiConnected"<<endl;
  118.     else
  119.         cout<<"The Graph is not BiConnected"<<endl;
  120.  
  121.     Graph g3(3);
  122.     g3.addEdge(0, 1);
  123.     g3.addEdge(1, 2);
  124.     if (g3.isBC())
  125.         cout<<"The Graph is BiConnected"<<endl;
  126.     else
  127.         cout<<"The Graph is not BiConnected"<<endl;
  128.  
  129.     Graph g4(5);
  130.     g4.addEdge(1, 0);
  131.     g4.addEdge(0, 2);
  132.     g4.addEdge(2, 1);
  133.     g4.addEdge(0, 3);
  134.     g4.addEdge(3, 4);
  135.     if (g4.isBC())
  136.         cout<<"The Graph is BiConnected"<<endl;
  137.     else
  138.         cout<<"The Graph is not BiConnected"<<endl;
  139.  
  140.     Graph g5(3);
  141.     g5.addEdge(0, 1);
  142.     g5.addEdge(1, 2);
  143.     g5.addEdge(2, 0);
  144.     if (g5.isBC())
  145.         cout<<"The Graph is BiConnected"<<endl;
  146.     else
  147.         cout<<"The Graph is not BiConnected"<<endl;
  148.  
  149.     return 0;
  150. }

advertisement
$ g++ biconnected.cpp
$ a.out
The Graph is BiConnected
The Graph is BiConnected
The Graph is not BiConnected
The Graph is not BiConnected
The Graph is BiConnected
 
 
------------------
(program exited with code: 0)
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
advertisement
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