Kosaraju's Strongly Connected Components Algorithm

Kosaraju’s Algorithm is a graph traversal algorithm used to find all strongly connected components (SCCs) present in a directed graph. The purpose of this algorithm is to efficiently identify the subsets/groups of vertices in a directed graph where each vertex in a subset is reachable from every other vertex within the same subset.

What are Strongly Connected Components?

Strongly connected components (SCCs) is a concept in graph theory used to describe subgraphs of a directed graph where every vertex in a subgraph is reachable from every other vertex within the same subgraph. In simpler terms, an SCC is a portion of the graph where you can travel between any two nodes in both directions without leaving the component. These components are important because they help to identify sections of a graph that are tightly interconnected, which can be useful for understanding the structure and behavior of networks, such as social networks or web pages.

Below is an illustration of a graph with each of its strongly connected components labeled:

Refer to this article to learn more about strongly connected components.

Detailed Steps of Kosaraju’s SCC Algorithm

Below are all the steps involved in Kosaraju’s algorithm:

Step 1: Perform first DFS and fill Post-Order Stack

Initialise a stack which stores nodes in post-order. Meaning, a node is added to the stack only after all the nodes connected to it are processed and added to the stack.
Perform a Depth-First Search (DFS) on the original graph.
Start from any unvisited vertex.
For each vertex:
- Mark it as visited.
- Recursively visit its unvisited neighbors.
- After processing all neighbors, push the vertex onto the stack.
The stack will contain vertices in post-order (reverse finish time).

Step 2: Graph Transposition (Creation of graph with reversed edges)

Create a new graph with the same vertices as the original.
For each edge (u, v) in the original graph, add edge (v, u) to the new graph.

Step 3: Perform Second DFS on the Transposed Graph

Initialize all vertices as unvisited.
While the stack from Step 1 is not empty:
- Pop a vertex from the stack.
- If the vertex is unvisited, start a new DFS from this vertex.
- Mark all vertices visited during this DFS as part of a new Strongly Connected Component.

Implementation of Kosaraju’s Algorithm


# Function to perform DFS and fill the post-order stack
def dfs1(graph, vertex, visited, stack):
  # Mark the current vertex as visited
  visited[vertex] = True

  # Recursively visit all unvisited neighbors
  for neighbor in graph[vertex]:
    if not visited[neighbor]:
      dfs1(graph, neighbor, visited, stack)

  # Push the current vertex onto the stack
  stack.append(vertex)

# Function to perform DFS on the transposed graph
def dfs2(graph, vertex, visited, scc):
  # Mark the current vertex as visited
  visited[vertex] = True

  # Add the current vertex to the current SCC
  scc.append(vertex)

  # Recursively visit all unvisited neighbors
  for neighbor in graph[vertex]:
    if not visited[neighbor]:
      dfs2(graph, neighbor, visited, scc)

# Function to find the strongly connected components
def find_strongly_connected_components(graph):
  # Step 1: Perform first DFS and fill the post-order stack
  visited = {vertex: False for vertex in graph}
  stack = []
  for vertex in graph:
    if not visited[vertex]:
      dfs1(graph, vertex, visited, stack)

  # Step 2: Create the transposed graph
  transposed_graph = {vertex: [] for vertex in graph}
  for vertex in graph:
    for neighbor in graph[vertex]:
      transposed_graph[neighbor].append(vertex)

  # Step 3: Perform second DFS on the transposed graph
  visited = {vertex: False for vertex in graph}
  strongly_connected_components = []
  while stack:
    vertex = stack.pop()
    if not visited[vertex]:
      # We came across a node in unvisited SCC
      current_scc = []
      dfs2(transposed_graph, vertex, visited, current_scc)
      strongly_connected_components.append(current_scc)

  return strongly_connected_components

graph = {
  "A": ["D", "B"],
  "B": ["C"],
  "C": ["A"],
  "D": ["I"],
  "E": ["D", "F"],
  "F": ["G"],
  "G": ["H"],
  "H": ["E"],
  "I": ["J"],
  "J": ["I"]
}

sccs = find_strongly_connected_components(graph)
for index, scc in enumerate(sccs):
  print(f"SCC-{index+1}: {scc}")


#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>

using namespace std;

// Function to perform DFS and fill the post-order stack
void dfs1(unordered_map<string, vector<string>>& graph, string vertex, unordered_map<string, bool>& visited, stack<string>& stack_) {
  // Mark the current vertex as visited
  visited[vertex] = true;

  // Recursively visit all unvisited neighbors
  for (const string& neighbor : graph[vertex]) {
    if (!visited[neighbor]) {
      dfs1(graph, neighbor, visited, stack_);
    }
  }

  // Push the current vertex onto the stack
  stack_.push(vertex);
}

// Function to perform DFS on the transposed graph
void dfs2(unordered_map<string, vector<string>>& graph, string vertex, unordered_map<string, bool>& visited, vector<string>& scc) {
  // Mark the current vertex as visited
  visited[vertex] = true;

  // Add the current vertex to the current SCC
  scc.push_back(vertex);

  // Recursively visit all unvisited neighbors
  for (const string& neighbor : graph[vertex]) {
    if (!visited[neighbor]) {
      dfs2(graph, neighbor, visited, scc);
    }
  }
}

// Function to find the strongly connected components
vector<vector<string>> find_strongly_connected_components(unordered_map<string, vector<string>>& graph) {
  // Step 1: Perform first DFS and fill the post-order stack
  unordered_map<string, bool> visited;
  stack<string> stack_;
  for (const auto& [vertex, _] : graph) {
    if (!visited[vertex]) {
      dfs1(graph, vertex, visited, stack_);
    }
  }

  // Step 2: Create the transposed graph
  unordered_map<string, vector<string>> transposed_graph;
  for (const auto& [vertex, neighbors] : graph) {
    for (const string& neighbor : neighbors) {
      transposed_graph[neighbor].push_back(vertex);
    }
  }

  // Step 3: Perform second DFS on the transposed graph
  visited.clear();
  vector<vector<string>> strongly_connected_components;
  while (!stack_.empty()) {
    string vertex = stack_.top();
    stack_.pop();
    if (!visited[vertex]) {
      // We came across a node in unvisited SCC
      vector<string> current_scc;
      dfs2(transposed_graph, vertex, visited, current_scc);
      strongly_connected_components.push_back(current_scc);
    }
  }

  return strongly_connected_components;
}

int main() {
  unordered_map<string, vector<string>> graph = {
    {"A", {"D", "B"}},
    {"B", {"C"}},
    {"C", {"A"}},
    {"D", {"I"}},
    {"E", {"D", "F"}},
    {"F", {"G"}},
    {"G", {"H"}},
    {"H", {"E"}},
    {"I", {"J"}},
    {"J", {"I"}}
  };

  vector<vector<string>> sccs = find_strongly_connected_components(graph);
  for (int i = 0; i < sccs.size(); i++) {
    cout << "SCC-" << i + 1 << ": ";
    for (const string& vertex : sccs[i]) {
      cout << vertex << " ";
    }
    cout << endl;
  }

  return 0;
}


// Function to perform DFS and fill the post-order stack
function dfs1(graph, vertex, visited, stack) {
  // Mark the current vertex as visited
  visited[vertex] = true;

  // Recursively visit all unvisited neighbors
  for (let neighbor of graph[vertex]) {
    if (!visited[neighbor]) {
      dfs1(graph, neighbor, visited, stack);
    }
  }

  // Push the current vertex onto the stack
  stack.push(vertex);
}

// Function to perform DFS on the transposed graph
function dfs2(graph, vertex, visited, scc) {
  // Mark the current vertex as visited
  visited[vertex] = true;

  // Add the current vertex to the current SCC
  scc.push(vertex);

  // Recursively visit all unvisited neighbors
  for (let neighbor of graph[vertex]) {
    if (!visited[neighbor]) {
      dfs2(graph, neighbor, visited, scc);
    }
  }
}

// Function to find the strongly connected components
function findStronglyConnectedComponents(graph) {
  // Step 1: Perform first DFS and fill the post-order stack
  let visited = {};
  for (let vertex in graph) {
    visited[vertex] = false;
  }
  let stack = [];
  for (let vertex in graph) {
    if (!visited[vertex]) {
      dfs1(graph, vertex, visited, stack);
    }
  }

  // Step 2: Create the transposed graph
  let transposedGraph = {};
  for (let vertex in graph) {
    transposedGraph[vertex] = [];
  }
  for (let vertex in graph) {
    for (let neighbor of graph[vertex]) {
      transposedGraph[neighbor].push(vertex);
    }
  }

  // Step 3: Perform second DFS on the transposed graph
  visited = {};
  for (let vertex in graph) {
    visited[vertex] = false;
  }
  let stronglyConnectedComponents = [];
  while (stack.length > 0) {
    let vertex = stack.pop();
    if (!visited[vertex]) {
      // We came across a node in unvisited SCC
      let currentScc = [];
      dfs2(transposedGraph, vertex, visited, currentScc);
      stronglyConnectedComponents.push(currentScc);
    }
  }

  return stronglyConnectedComponents;
}

let graph = {
  "A": ["D", "B"],
  "B": ["C"],
  "C": ["A"],
  "D": ["I"],
  "E": ["D", "F"],
  "F": ["G"],
  "G": ["H"],
  "H": ["E"],
  "I": ["J"],
  "J": ["I"]
};

let sccs = findStronglyConnectedComponents(graph);
for (let i = 0; i < sccs.length; i++) {
  console.log(`SCC-${i+1}: ${sccs[i]}`);
}


import java.util.*;

public class Main {
  // Function to perform DFS and fill the post-order stack
  private static void dfs1(Map<String, List<String>> graph, String vertex, Map<String, Boolean> visited, Stack<String> stack) {
    // Mark the current vertex as visited
    visited.put(vertex, true);

    // Recursively visit all unvisited neighbors
    for (String neighbor : graph.get(vertex)) {
      if (!visited.getOrDefault(neighbor, false)) {
        dfs1(graph, neighbor, visited, stack);
      }
    }

    // Push the current vertex onto the stack
    stack.push(vertex);
  }

  // Function to perform DFS on the transposed graph
  private static void dfs2(Map<String, List<String>> graph, String vertex, Map<String, Boolean> visited, List<String> scc) {
    // Mark the current vertex as visited
    visited.put(vertex, true);

    // Add the current vertex to the current SCC
    scc.add(vertex);

    // Recursively visit all unvisited neighbors
    for (String neighbor : graph.get(vertex)) {
      if (!visited.getOrDefault(neighbor, false)) {
        dfs2(graph, neighbor, visited, scc);
      }
    }
  }

  // Function to find the strongly connected components
  public static List<List<String>> findStronglyConnectedComponents(Map<String, List<String>> graph) {
    // Step 1: Perform first DFS and fill the post-order stack
    Map<String, Boolean> visited = new HashMap<>();
    Stack<String> stack = new Stack<>();
    for (String vertex : graph.keySet()) {
      if (!visited.getOrDefault(vertex, false)) {
        dfs1(graph, vertex, visited, stack);
      }
    }

    // Step 2: Create the transposed graph
    Map<String, List<String>> transposedGraph = new HashMap<>();
    for (String vertex : graph.keySet()) {
      transposedGraph.put(vertex, new ArrayList<>());
    }
    for (String vertex : graph.keySet()) {
      for (String neighbor : graph.get(vertex)) {
        transposedGraph.get(neighbor).add(vertex);
      }
    }

    // Step 3: Perform second DFS on the transposed graph
    visited = new HashMap<>();
    List<List<String>> stronglyConnectedComponents = new ArrayList<>();
    while (!stack.isEmpty()) {
      String vertex = stack.pop();
      if (!visited.getOrDefault(vertex, false)) {
        // We came across a node in unvisited SCC
        List<String> currentScc = new ArrayList<>();
        dfs2(transposedGraph, vertex, visited, currentScc);
        stronglyConnectedComponents.add(currentScc);
      }
    }

    return stronglyConnectedComponents;
  }

  public static void main(String[] args) {
    Map<String, List<String>> graph = new HashMap<>();
    graph.put("A", Arrays.asList("D", "B"));
    graph.put("B", Arrays.asList("C"));
    graph.put("C", Arrays.asList("A"));
    graph.put("D", Arrays.asList("I"));
    graph.put("E", Arrays.asList("D", "F"));
    graph.put("F", Arrays.asList("G"));
    graph.put("G", Arrays.asList("H"));
    graph.put("H", Arrays.asList("E"));
    graph.put("I", Arrays.asList("J"));
    graph.put("J", Arrays.asList("I"));

    List<List<String>> sccs = findStronglyConnectedComponents(graph);
    for (int i = 0; i < sccs.size(); i++) {
      System.out.println("SCC-" + (i + 1) + ": " + sccs.get(i));
    }
  }
}

Time and Space Complexity

Time Complexity:

The time complexity of Kosaraju’s algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Step-1 of the algorithm involves DFS traversal which takes O(V + E) time.
Step-2 of the algorithm involved transposing the graph (reverse the direction of all edges) which takes O(V + E) time.
Step-3 and Step-4 involves another DFS on the transposed graph which again takes O(V + E) time.

The total time complexity of Kosaraju’s algorithm is the sum of the time complexities of these three steps, which is O(V + E).

Space Complexity:

Kosaraju’s algorithm requires O(V) space to store all the nodes in the graph in post-order. Additionally, the algorithm requires O(V+E) space for storing the transposed graph. So in all, the algorithm requires O(V+E) space where V is the number of vertices and E is the number of edges in the graph.

Intuition Behind the Algorithm

To understand how Kosaraju’s algorithm works, it’s important to understand the order in which Depth First Search (DFS) visits the nodes in a graph. You can refer to this article to understand more about Depth First Search if you are new to this concept.

Let’s consider the example graph below to understand how strongly connected components can be grouped using DFS.

If you start DFS from any node in SSC-1, you will be able to reach all the nodes present in SCC-1, SCC-2 and SCC-3. You can’t reach SCC-4 because there is no path from any node present in SCC-1 to a node present in SCC-4.

But, if you start DFS from any node in SCC-3, only the nodes present in that component will be visited in the DFS iteration as there is no edge flowing out of SCC-3. So all the nodes visited in this DFS iteration can be considered as belonging to one strongly connected component. Below are the remaining components after this DFS iteration:

Strongly Connected Component identified in this DFS iteration: SCC-3 with nodes {I, J}

Now, if you start DFS from any node in SCC-1 or SCC-4, you will also reach nodes in SCC-2. So these nodes are not a good place to start the next DFS. But, if you start DFS from any node in SCC-2, you will only visit nodes in that strongly connected component. Even though there is path to SCC-3, we would consider those nodes as they are already identified as a separated strongly connected component. Below are this remaining components after this DFS iteration:

Strongly Connected Component identified in this DFS iteration: SCC-2 with nodes {D}

Now we can perform DFS from any node in SCC-1 and add all nodes visited to another strongly connected component. Below are this remaining components after this DFS iteration:

Strongly Connected Component identified in this DFS iteration: SCC-1 with nodes {A,B,C}

Finally we can perform DFS from any node present in SCC-4 and add all nodes visited to another strongly connected component. After this DFS iteration, all the nodes in the graph are categorised into strongly connected components.

Strongly Connected Component identified in this DFS iteration: SCC-4 with nodes {E,F,G,H}

The pattern is that if you perform DFS from any node in a strongly connected component which does not have any outward edge to any other active component in the graph, only the nodes in that component will be covered in the DFS iteration. If we keep doing this, we get all nodes in a strongly connected component with each DFS iteration.

Kosaraju’s algorithm identifies all strongly connected components using the same principle but in a slightly different way. It first performs DFS from a random node in the graph and stores all nodes in a stack in post-order, meaning a node is added to the stack only after all nodes reachable from it have been visited. Because of this, the nodes from which there are paths to other components will be at the top of the stack. Due to reversal of all edges in the graph in the next step, the nodes present at the top of stack will be the ones from which there won’t be any outward paths to other unvisited components in the reversed graph.

Because of this, in each DFS iteration performed in Kosaraju’s algorithm on the transposed graph, all nodes belonging to a specific strongly connected component will be visited/identified.