C++ Program to Check if a Directed Graph is Strongly or Weakly Connected

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

Here is source code of the C++ Program to Check Whether it is Weakly Connected or Strongly Connected for a Directed Graph. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

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

Output:

advertisement
$ g++ StronglyWeaklyConnectedGraph.cpp
$ a.out
 
Following are strongly connected components in given graph 
0 1 2 
3 
4 
Graph is weakly connected.
------------------
(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.