Strongly Connected Components
A strongly connected component (SCC) is a maximal set of vertices where every vertex is reachable from every other. Kosaraju's algorithm finds SCCs in O(V+E) using two DFS passes.
Kosaraju's Algorithm:
1. Perform DFS on original graph, push nodes to stack in order of completion.
2. Transpose the graph (reverse all edges).
3. Pop nodes from stack, run DFS on transposed graph to get each SCC.
Java implementation (using adjacency list):
public void kosarajuSCC() {
Stack stack = new Stack<>();
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) dfsFillOrder(i, visited, stack);
}
List[] transpose = getTranspose();
Arrays.fill(visited, false);
while (!stack.isEmpty()) {
int v = stack.pop();
if (!visited[v]) {
dfsUtil(transpose, v, visited);
System.out.println();
}
}
}
Two Minute Drill
- SCC: maximal set where every vertex reachable from others.
- Kosaraju's algorithm uses two DFS passes on original and transpose graph.
- Time O(V+E), space O(V+E).
- Used in social network analysis, circuit design.
Need more clarification?
Drop us an email at career@quipoinfotech.com