What is a Strongly Connected Component in Data Structure? | Data Structure Tutorial

Strongly Connected Component in Data Structure

In this article, you will learn about how strongly connected components are formed. 

A strongly connected component is the part of a directed graph in which it forms a path from each vertex to another vertex. It is applicable only on a directed graph. 

Let’s consider a graph:

In the above example, you can see each vertex is reaching the other vertex through the directed graph. These components are found using Kosaraju’s Algorithm.

Kosaraju’s Algorithm

The kosaraju’s Algorithm is based on the depth-first search algorithm and it is implemented twice.

The steps are involved.

1. Execute a depth-first search on the complete graph. Start from vertex-0, check the connection with its child vertices, and mark the visited vertices as done. If a vertex leads to an already visited vertex, then push this vertex to the stack.
2. Reverse the original graph.
3. Execute the depth-first search on the reversed graph. Start from the first vertex of the stack. Traverse through all of its child vertices. Once you reach the already visited vertex, the one strongly connected component is formed.
4. Thus, it will show the strongly connected components.

Kosaraju’s Algorithm Complexity

It runs in linear time i.e 0(V+E).

The applications of the strongly connected components:

• Vehicle routing application
• Maps application
• Model-checking in formal verification