C++ Program to Check if a Directed Graph is Weakly Connected or Not using DFS

This is a C++ Program to check whether a directed graph is weakly connected or not. We can do DFS V times starting from every vertex. If any DFS, doesn’t visit all vertices, then graph is not strongly connected. This algorithm takes O(V*(V+E)) time which can be same as transitive closure for a dense graph.Time complexity of above implementation is sane as Depth First Search which is O(V+E) if the graph is represented using adjacency matrix representation.

Here is source code of the C++ Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. // Program to check if a given directed graph is strongly connected or not
  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.         // A recursive function to print DFS starting from v
  13.         void DFSUtil(int v, bool visited[]);
  14.     public:
  15.         // Constructor and Destructor
  16.         Graph(int V)
  17.         {
  18.             this->V = V;
  19.             adj = new list<int> [V];
  20.         }
  21.         ~Graph()
  22.         {
  23.             delete[] adj;
  24.         }
  25.  
  26.         // Method to add an edge
  27.         void addEdge(int v, int w);
  28.  
  29.         // The main function that returns true if the graph is strongly
  30.         // connected, otherwise false
  31.         bool isSC();
  32.  
  33.         // Function that returns reverse (or transpose) of this graph
  34.         Graph getTranspose();
  35. };
  36.  
  37. // A recursive function to print DFS starting from v
  38. void Graph::DFSUtil(int v, bool visited[])
  39. {
  40.     // Mark the current node as visited and print it
  41.     visited[v] = true;
  42.  
  43.     // Recur for all the vertices adjacent to this vertex
  44.     list<int>::iterator i;
  45.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  46.         if (!visited[*i])
  47.             DFSUtil(*i, visited);
  48. }
  49.  
  50. // Function that returns reverse (or transpose) of this graph
  51. Graph Graph::getTranspose()
  52. {
  53.     Graph g(V);
  54.     for (int v = 0; v < V; v++)
  55.     {
  56.         // Recur for all the vertices adjacent to this vertex
  57.         list<int>::iterator i;
  58.         for (i = adj[v].begin(); i != adj[v].end(); ++i)
  59.         {
  60.             g.adj[*i].push_back(v);
  61.         }
  62.     }
  63.     return g;
  64. }
  65.  
  66. void Graph::addEdge(int v, int w)
  67. {
  68.     adj[v].push_back(w); // Add w to v’s list.
  69. }
  70.  
  71. // The main function that returns true if graph is strongly connected
  72. bool Graph::isSC()
  73. {
  74.     // St1p 1: Mark all the vertices as not visited (For first DFS)
  75.     bool visited[V];
  76.     for (int i = 0; i < V; i++)
  77.         visited[i] = false;
  78.  
  79.     // Step 2: Do DFS traversal starting from first vertex.
  80.     DFSUtil(0, visited);
  81.  
  82.     // If DFS traversal doesn’t visit all vertices, then return false.
  83.     for (int i = 0; i < V; i++)
  84.         if (visited[i] == false)
  85.             return false;
  86.  
  87.     // Step 3: Create a reversed graph
  88.     Graph gr = getTranspose();
  89.  
  90.     // Step 4: Mark all the vertices as not visited (For second DFS)
  91.     for (int i = 0; i < V; i++)
  92.         visited[i] = false;
  93.  
  94.     // Step 5: Do DFS for reversed graph starting from first vertex.
  95.     // Staring Vertex must be same starting point of first DFS
  96.     gr.DFSUtil(0, visited);
  97.  
  98.     // If all vertices are not visited in second DFS, then
  99.     // return false
  100.     for (int i = 0; i < V; i++)
  101.         if (visited[i] == false)
  102.             return false;
  103.  
  104.     return true;
  105. }
  106.  
  107. // Driver program to test above functions
  108. int main()
  109. {
  110.     // Create graphs given in the above diagrams
  111.     Graph g1(5);
  112.     g1.addEdge(0, 1);
  113.     g1.addEdge(1, 2);
  114.     g1.addEdge(2, 3);
  115.     g1.addEdge(3, 0);
  116.     g1.addEdge(2, 4);
  117.     g1.addEdge(4, 2);
  118.     cout << "The graph is weakly connected? ";
  119.     g1.isSC() ? cout << "No\n" : cout << "Yes\n";
  120.  
  121.     Graph g2(4);
  122.     g2.addEdge(0, 1);
  123.     g2.addEdge(1, 2);
  124.     g2.addEdge(2, 3);
  125.     cout << "The graph is weakly connected? ";
  126.     g2.isSC() ? cout << "No\n" : cout << "Yes\n";
  127.  
  128.     return 0;
  129. }

Output:

$ g++ WeaklyConnectedDFS.cpp
$ a.out
 
The graph is weakly connected? No
The graph is weakly connected? Yes
 
------------------
(program exited with code: 0)
Press return to continue

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

advertisement
advertisement

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

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.