Understanding the Problem
In a directed graph, a Strongly Connected Component (SCC) is a group of vertices where every vertex is reachable from every other vertex in that group.
In simpler terms, if you can start at any node in the group and reach all the others through the directed edges—and also get back to the starting node—then those nodes form an SCC.
Our goal is to identify all such strongly connected components in a given directed graph. We'll solve this using Kosaraju's Algorithm, which is efficient and beginner-friendly once understood step-by-step.
Step-by-Step Solution with Example
Step 1: Do a DFS on the original graph and record finish times
Start by doing a standard DFS traversal of the graph. As we finish exploring each node (i.e., all its neighbors are visited), we push it onto a stack.
This stack captures the nodes in the order of their finishing times—the last finished node ends up on top.
Why? This helps us process nodes in the right order during the second DFS on the transposed graph.
Step 2: Transpose the graph (reverse all edges)
Next, we reverse all the directed edges in the graph. That is, if there was an edge from A → B, in the transposed graph it becomes B → A.
This reversal helps us discover which nodes can be reached in reverse direction, a key aspect in identifying SCCs.
Step 3: Do DFS on the transposed graph using the stack order
Now, we pop nodes one by one from the stack and perform DFS on the transposed graph.
Each time we start a new DFS from an unvisited node, we find one SCC—all the nodes reached in this DFS form a strongly connected component.
Since the stack ensures we process nodes in decreasing order of finish times, we are guaranteed that whenever we start a new DFS, we start from a root node of some SCC.
Example: Step-by-step on a sample graph
Graph:
Vertices = {0, 1, 2, 3, 4}
Edges = {
0 → 2,
2 → 1,
1 → 0,
0 → 3,
3 → 4
}
Step 1: DFS Finish Order (pushed to stack): [4, 3, 0, 1, 2]
Step 2: Transpose Graph:
2 → 0
1 → 2
0 → 1
3 → 0
4 → 3
Step 3: DFS on Transposed Graph in Stack Order:
- Start DFS from 2 → reaches 2, 1, 0 → SCC1 = [2,1,0]
- Next node in stack is 1 → already visited
- Next is 0 → already visited
- Next is 3 → reaches 3 → SCC2 = [3]
- Next is 4 → reaches 4 → SCC3 = [4]
Final SCCs: [2,1,0], [3], [4]
Edge Cases
- Empty Graph: No vertices means no SCCs to find.
- Single Node: A single node with or without a self-loop is an SCC by itself.
- Disconnected Nodes: Nodes with no outgoing or incoming edges form their own SCCs.
- Multiple Cycles: Kosaraju's algorithm naturally groups cycles correctly into separate SCCs.
Finally
Kosaraju’s Algorithm is a powerful and intuitive method to identify strongly connected components.
Its beauty lies in the simplicity of using two DFS traversals—first to record finish order, and second to explore reversed connectivity.
It runs in linear time O(V + E)
, making it suitable even for large graphs.
As you work through the steps, always remember that SCCs are about mutual reachability, and DFS with finish order is the key to unlocking that structure.
Comments
Loading comments...