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.

// Program to check if a given directed graph is strongly connected or not

```
#include <iostream>
```
```
#include <list>
```
```
#include <stack>
```
```
using namespace std;
```
```
 
```
```
class Graph
```
```
{
```
```
        int V; // No. of vertices
```

        list<int> *adj; // An array of adjacency lists

```
 
```

        // A recursive function to print DFS starting from v

        void DFSUtil(int v, bool visited[]);

```
    public:
```
```
        // Constructor and Destructor
```
```
        Graph(int V)
```
```
        {
```
```
            this->V = V;
```
```
            adj = new list<int> [V];
```
```
        }
```
```
        ~Graph()
```
```
        {
```
```
            delete[] adj;
```
```
        }
```
```
 
```
```
        // Method to add an edge
```
```
        void addEdge(int v, int w);
```
```
 
```

        // The main function that returns true if the graph is strongly

```
        // connected, otherwise false
```
```
        bool isSC();
```
```
 
```

        // Function that returns reverse (or transpose) of this graph

```
        Graph getTranspose();
```
```
};
```
```
 
```

// A recursive function to print DFS starting from v

void Graph::DFSUtil(int v, bool visited[])

```
{
```

    // Mark the current node as visited and print it

```
    visited[v] = true;
```
```
 
```

    // Recur for all the vertices adjacent to this vertex

```
    list<int>::iterator i;
```

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

```
        if (!visited[*i])
```
```
            DFSUtil(*i, visited);
```
```
}
```
```
 
```

// Function that returns reverse (or transpose) of this graph

```
Graph Graph::getTranspose()
```
```
{
```
```
    Graph g(V);
```
```
    for (int v = 0; v < V; v++)
```
```
    {
```

        // Recur for all the vertices adjacent to this vertex

```
        list<int>::iterator i;
```

        for (i = adj[v].begin(); i != adj[v].end(); ++i)

```
        {
```
```
            g.adj[*i].push_back(v);
```
```
        }
```
```
    }
```
```
    return g;
```
```
}
```
```
 
```
```
void Graph::addEdge(int v, int w)
```
```
{
```

    adj[v].push_back(w); // Add w to v’s list.

```
}
```
```
 
```

// The main function that returns true if graph is strongly connected

```
bool Graph::isSC()
```
```
{
```

    // St1p 1: Mark all the vertices as not visited (For first DFS)

```
    bool visited[V];
```
```
    for (int i = 0; i < V; i++)
```
```
        visited[i] = false;
```
```
 
```

    // Step 2: Do DFS traversal starting from first vertex.

```
    DFSUtil(0, visited);
```
```
 
```

    // If DFS traversal doesn’t visit all vertices, then return false.

```
    for (int i = 0; i < V; i++)
```
```
        if (visited[i] == false)
```
```
            return false;
```
```
 
```
```
    // Step 3: Create a reversed graph
```
```
    Graph gr = getTranspose();
```
```
 
```

    // Step 4: Mark all the vertices as not visited (For second DFS)

```
    for (int i = 0; i < V; i++)
```
```
        visited[i] = false;
```
```
 
```

    // Step 5: Do DFS for reversed graph starting from first vertex.

    // Staring Vertex must be same starting point of first DFS

```
    gr.DFSUtil(0, visited);
```
```
 
```

    // If all vertices are not visited in second DFS, then

```
    // return false
```
```
    for (int i = 0; i < V; i++)
```
```
        if (visited[i] == false)
```
```
            return false;
```
```
 
```
```
    return true;
```
```
}
```
```
 
```

// Driver program to test above functions

```
int main()
```
```
{
```

    // Create graphs given in the above diagrams

```
    Graph g1(5);
```
```
    g1.addEdge(0, 1);
```
```
    g1.addEdge(1, 2);
```
```
    g1.addEdge(2, 3);
```
```
    g1.addEdge(3, 0);
```
```
    g1.addEdge(2, 4);
```
```
    g1.addEdge(4, 2);
```

    cout << "The graph is weakly connected? ";

    g1.isSC() ? cout << "No\n" : cout << "Yes\n";

```
 
```
```
    Graph g2(4);
```
```
    g2.addEdge(0, 1);
```
```
    g2.addEdge(1, 2);
```
```
    g2.addEdge(2, 3);
```

    cout << "The graph is weakly connected? ";

    g2.isSC() ? cout << "No\n" : cout << "Yes\n";

```
 
```
```
    return 0;
```
```
}
```

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.

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

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

» Next - C++ Program to Implement Dijkstra’s Algorithm using Set

Related Posts:

Recommended Articles: