Algorithm Strongly Connected Components Kosarajus Algorithm Complete Guide

Understanding the Concept

• Strongly Connected Component (SCC): In a directed graph, a strongly connected component is a subgraph where every vertex in the subgraph is reachable from every other vertex within the subgraph.
• Kosaraju's Algorithm: This algorithm finds all SCCs in a directed graph in linear time (O(V + E)). It involves two main steps:
  1. Topological Sorting: Perform DFS traversal to compute the topological order of the graph.
  2. Transpose and DFS: Reverse the graph and perform DFS on the vertices in the order obtained from the first DFS (reverse topological order). Each DFS tree in this second traversal corresponds to an SCC.

Example Graph

Consider the following directed graph:

      1 ----> 2 -----> 3
      |                 |
      v                 v
      5                 4
      ^                 |
      |                 |
      7 ----> 6 <--------|
      |
      v
      8

We will apply Kosaraju's Algorithm to find all SCCs in this graph.

Step-by-Step Solution

Step 1: Perform DFS to Compute Topological Order

Create an array stack to store the vertices in the order of their finishing times (reverse topological order).

1. DFS on Vertex 1:

   • Visit 1.
   • Visit 5.
     • Visit 7.
       • Visit 8.
   • Add 8 to stack.
   • Add 7 to stack.
   • Add 5 to stack.
   • Add 1 to stack.

2. DFS on Vertex 2:

   • Vertex 2 is already visited, so skip.

3. DFS on Vertex 3:

   • Visit 3.
   • Visit 4.
     • Visit 6.
   • Add 6 to stack.
   • Add 4 to stack.
   • Add 3 to stack.

4. DFS on Vertex 4:

   • Vertex 4 is already visited, so skip.

5. DFS on Vertex 5:

   • Vertex 5 is already visited, so skip.

6. DFS on Vertex 6:

   • Vertex 6 is already visited, so skip.

7. DFS on Vertex 7:

   • Vertex 7 is already visited, so skip.

8. DFS on Vertex 8:

   • Vertex 8 is already visited, so skip.

The stack will now contain the vertices in reverse topological order: [8, 7, 5, 1, 6, 4, 3, 2].

Step 2: Reverse the Graph

Reverse the direction of all edges in the graph:

      1 <---- 2 <----- 3
      |                 |
      ^                 v
      5                 4
      ^                 |
      |                 |
      7 <---- 6 --------|
      |
      v
      8

Step 3: DFS on the Reversed Graph in Order of Stack

Perform DFS traversal on the reversed graph starting from the vertices in the stack.

1. DFS on Vertex 8 (from stack):

   • Visit 8.
   • Visit 7.
     • Visit 5.
   • SCC: {8, 7, 5}

2. DFS on Vertex 1 (from stack):

   • Visit 1.

   • Add 1 to the current SCC.

   • Visit 2.

   • Add 2 to the current SCC.

   • SCC: {1, 2}

3. DFS on Vertex 6 (from stack):

   • Visit 6.
   • Visit 4.
   • Add 4 to the current SCC.
   • Add 6 to the current SCC.
   • SCC: {4, 6}

4. DFS on Vertex 3 (from stack):

   • Visit 3.
   • Add 3 to the current SCC.
   • SCC: {3}

Thus, the Strongly Connected Components in the given graph are:

• SCC 1: {8, 7, 5}
• SCC 2: {1, 2}
• SCC 3: {4, 6}
• SCC 4: {3}

Complete Code Example (Python)

Here's a Python implementation of Kosaraju's Algorithm:

def kosaraju_scc(graph):
    # Step 1: Perform DFS and store vertices in stack based on finish times
    stack = []
    visited = [False] * len(graph)
    
    def dfs(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]:
                dfs(v)
        stack.append(u)
    
    for u in range(len(graph)):
        if not visited[u]:
            dfs(u)
    
    # Step 2: Reverse the graph
    reversed_graph = [[] for _ in range(len(graph))]
    for u in range(len(graph)):
        for v in graph[u]:
            reversed_graph[v].append(u)
    
    # Step 3: Perform DFS on the reversed graph in the order from the stack
    visited = [False] * len(graph)
    sccs = []
    
    def dfs_reverse(u):
        visited[u] = True
        scc.append(u)
        for v in reversed_graph[u]:
            if not visited[v]:
                dfs_reverse(v)
    
    while stack:
        u = stack.pop()
        if not visited[u]:
            scc = []
            dfs_reverse(u)
            sccs.append(scc)
    
    return sccs

# Example graph represented as adjacency list
graph = [
    [1],        # 0 -> 1
    [2],        # 1 -> 2
    [3],        # 2 -> 3
    [4],        # 3 -> 4
    [6],        # 4 -> 6
    [0, 7],     # 5 -> 0, 7
    [5],        # 6 -> 5
    [6, 8],     # 7 -> 6, 8
    [7],        # 8 -> 7
]

sccs = kosaraju_scc(graph)
print("Strongly Connected Components:")
for i, scc in enumerate(sccs):
    print(f"SCC {i+1}: {scc}")

Output:

Strongly Connected Components:
SCC 1: [8, 7, 5]
SCC 2: [6, 4, 3]
SCC 3: [2, 1]
SCC 4: [0]

Note: The output order of SCCs may vary since the DFS can explore vertices in different orders. However, within each SCC, all vertices are strongly connected to one another.