Check if Graph is Strongly Connected or not using one DFS Traversal

Given a directed graph, check if it is strongly connected or not. A directed graphs is said to be strongly connected if every vertex is reachable from every other vertex.

 
For example,

 
Below graph is strongly connected as path exists between all pairs of vertices.

 
  strongly connected graph

 


 

Prerequisite:

1. Arrival Time & Departure Time of Vertices in DFS

2. Types of edges involved in DFS and relation between them

 

In previous post, we have discussed a solution for that requires two DFS traversals of a Graph. We can check if graph is strongly connected or not by doing only one DFS traversal of the graph.

When we do a DFS from a vertex v in an directed graph, there could be many edges going out of its sub tree. When we say subtree rooted at v, we mean all v’s descendants including the vertex itself. The edges which are going out of the sub tree will either be a back edge or a cross edge. Forward edge cannot be going out of the sub tree as they can only be coming in to the sub tree or if it starts from within the sub tree it will go within the sub tree only.

We can say that the graph is strongly connected if and only if for every edge u->v in the graph, there is at-least one back-edge or cross-edge that is going out of subtree rooted at v.

 

How should we modify DFS so that we can check if there is a out-edge going out of every sub tree?

 

We can modify DFS such that DFS(v) returns the smallest arrival time to which there is an out-edge from the sub tree rooted at v. For example, let arrival(v) be the arrival time of vertex v in the DFS. Then if there is a edge out of the sub tree rooted at v, it’s to something visited before v & therefore with a smaller arrival value.

Remember for a back edge or cross edge u -> v,arrival[u] > arrival[v]

Suppose there are four edges going out of sub-tree rooted at v to vertex a, b, c and d and with arrival time arrival(a), arrival(b), arrival(c) and arrival(d) respectively. We look at their four arrival times & consider the smallest among them and that will be the value returned by DFS(v). i.e. DFS(v) returns min of arrival(a), arrival(b), arrival(c) and arrival(d). But before returning, we have to check that min(arrival(a), arrival(b), arrival(c), arrival(d)) is less than the arrival(v). If min(arrival(a), arrival(b), arrival(c), arrival(d)) is less than the arrival(v), then that means that at-least one back-edge or cross edge is going out of the sub tree rooted at v. If not, then we can stop the procedure and say that the graph is not strongly connected.

 
C++ implementation –

Download   Run Code

Output:

Graph is Strongly Connected

 
Time complexity of above solutions is O(n + m) where n is number of vertices and e is number of edges in the graph. Please note that O(m) may vary between O(1) and O(n2), depending on how dense the graph is.

 
Reference: Dr. Naveen garg, IIT-D (Lecture – 30 Applications of DFS in Directed Graphs)

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz