C++ Program to Find the Connected Components in an UnDirected Graph

«
»
This is a C++ Program to find the connected components of the undirected graph. This can be done using depth first search

Here is source code of the C++ Program to Find the Connected Components of an UnDirected Graph. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. // Implementation of Kosaraju's algorithm to print all SCCs
  2. #include <iostream>
  3. #include <list>
  4. #include <stack>
  5. using namespace std;
  6.  
  7. class Graph
  8. {
  9.         int V; // No. of vertices
  10.         list<int> *adj; // An array of adjacency lists
  11.  
  12.         // Fills Stack with vertices (in increasing order of finishing times)
  13.         // The top element of stack has the maximum finishing time
  14.         void fillOrder(int v, bool visited[], stack<int> &Stack);
  15.  
  16.         // A recursive function to print DFS starting from v
  17.         void DFSUtil(int v, bool visited[]);
  18.     public:
  19.         Graph(int V);
  20.         void addEdge(int v, int w);
  21.  
  22.         // The main function that finds and prints strongly connected components
  23.         int printSCCs();
  24.  
  25.         // Function that returns reverse (or transpose) of this graph
  26.         Graph getTranspose();
  27. };
  28.  
  29. Graph::Graph(int V)
  30. {
  31.     this->V = V;
  32.     adj = new list<int> [V];
  33. }
  34.  
  35. // A recursive function to print DFS starting from v
  36. void Graph::DFSUtil(int v, bool visited[])
  37. {
  38.     // Mark the current node as visited and print it
  39.     visited[v] = true;
  40.     cout << v << " ";
  41.  
  42.     // Recur for all the vertices adjacent to this vertex
  43.     list<int>::iterator i;
  44.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  45.         if (!visited[*i])
  46.             DFSUtil(*i, visited);
  47. }
  48.  
  49. Graph Graph::getTranspose()
  50. {
  51.     Graph g(V);
  52.     for (int v = 0; v < V; v++)
  53.     {
  54.         // Recur for all the vertices adjacent to this vertex
  55.         list<int>::iterator i;
  56.         for (i = adj[v].begin(); i != adj[v].end(); ++i)
  57.         {
  58.             g.adj[*i].push_back(v);
  59.         }
  60.     }
  61.     return g;
  62. }
  63.  
  64. void Graph::addEdge(int v, int w)
  65. {
  66.     adj[v].push_back(w); // Add w to v’s list.
  67. }
  68.  
  69. void Graph::fillOrder(int v, bool visited[], stack<int> &Stack)
  70. {
  71.     // Mark the current node as visited and print it
  72.     visited[v] = true;
  73.  
  74.     // Recur for all the vertices adjacent to this vertex
  75.     list<int>::iterator i;
  76.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  77.         if (!visited[*i])
  78.             fillOrder(*i, visited, Stack);
  79.  
  80.     // All vertices reachable from v are processed by now, push v to Stack
  81.     Stack.push(v);
  82. }
  83.  
  84. // The main function that finds and prints all strongly connected components
  85. int Graph::printSCCs()
  86. {
  87.     stack<int> Stack;
  88.  
  89.     // Mark all the vertices as not visited (For first DFS)
  90.     bool *visited = new bool[V];
  91.     for (int i = 0; i < V; i++)
  92.         visited[i] = false;
  93.  
  94.     // Fill vertices in stack according to their finishing times
  95.     for (int i = 0; i < V; i++)
  96.         if (visited[i] == false)
  97.             fillOrder(i, visited, Stack);
  98.  
  99.     // Create a reversed graph
  100.     Graph gr = getTranspose();
  101.  
  102.     // Mark all the vertices as not visited (For second DFS)
  103.     for (int i = 0; i < V; i++)
  104.         visited[i] = false;
  105.     int count = 0;
  106.     // Now process all vertices in order defined by Stack
  107.     while (Stack.empty() == false)
  108.     {
  109.         // Pop a vertex from stack
  110.         int v = Stack.top();
  111.         Stack.pop();
  112.  
  113.         // Print Strongly connected component of the popped vertex
  114.         if (visited[v] == false)
  115.         {
  116.             gr.DFSUtil(v, visited);
  117.             cout << endl;
  118.         }
  119.         count++;
  120.     }
  121.     return count;
  122. }
  123.  
  124. // Driver program to test above functions
  125. int main()
  126. {
  127.     // Create a graph given in the above diagram
  128.     Graph g(5);
  129.     g.addEdge(1, 0);
  130.     g.addEdge(0, 2);
  131.     g.addEdge(2, 1);
  132.     g.addEdge(0, 3);
  133.     g.addEdge(3, 4);
  134.  
  135.     cout << "Following are strongly connected components in given graph \n";
  136.     if (g.printSCCs() > 1)
  137.     {
  138.         cout << "Graph is weakly connected.";
  139.     }
  140.     else
  141.     {
  142.         cout << "Graph is strongly connected.";
  143.     }
  144.  
  145.     return 0;
  146. }

Output:

advertisement
$ g++ CheckStronglyConnected.cpp
$ a.out
 
Following are strongly connected components in given graph 
0 1 2 
3 
4 
 
------------------
(program exited with code: 0)
Press return to continue

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

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

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 & technical discussions at Telegram SanfoundryClasses.