Strongly Connected Components

Strongly Connected Components

Connectivity in an undirected graph means that every vertex can reach every other vertex via any path. If the graph is not connected the graph can be broken down into Connected Components.

Strong Connectivity applies only to directed graphs. A directed graph is strongly connected if there is a directed path from any vertex to every other vertex. This is same as connectivity in an undirected graph, the only difference being strong connectivity applies to directed graphs and there should be directed paths instead of just paths.

A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.

For example, there are 3 SCCs in the above graph.

We can find all strongly connected components in O(V+E) time using Kosaraju’s algorithm.

Following is detailed Kosaraju’s algorithm.

1) Create an empty stack ‘S’ and do DFS traversal of a graph. In DFS traversal, after calling recursive DFS for adjacent vertices of a vertex, push the vertex to stack.

In the above graph, if we start DFS from vertex 0, we get 0→3→4→2→1. So, we get vertices  as 1, 2, 4, 3, 0 in stack

2) Reverse directions of all arcs to obtain the transpose graph.

3) One by one pop a vertex from S while S is not empty. Let the popped vertex be ‘v’. Take v as source and do DFS. The DFS starting from v prints strongly connected component of v.

In the above example, we process vertices in order 0→2→1, 3, 4.

So the strongly connected components in the given graph are: 021, 3, and 4.