Strongly Connected Components

Written by Charlotte Knierim.

Contents

Algorithm by Kosaraju
- Implementation

This article assumes you are familiar with digraphs (directed graphs) and have already read the article about Preorder and Postorder.

In this article we look at strongly connected components of digraphs. Given a digraph, it is a natural question which vertices can be reached by a given vertex. A digraph is called strongly connected, if every vertex can be reached from every other vertex.

If a digraph is not strongly connected, then we can decompose it into strongly connected components. These are maximal sets in the graph such that every vertex in a set can be reached by every other vertex from the same set.

Example:

We can display the relationship between the strongly connected components in a component graph. The component graph is a DAG (directed acyclic graph). Note that there is a path from vertex $u$ to vertex $v$ if and only if there is a path from the component containing $u$ to the component containing $v$ in the component graph.

Example:

Algorithm by Kosaraju

We show an algorithm that computes the strongly connected components of a digraph $D=(V,E)$ in $O(V+E)$ . For this algorithm, we need the transpose $D^T =(V,E^T)$ that consists of all edges of $D$ reversed. Formally we add an edge $(u,v)$ to $E^T$ if $(v,u)$ was an edge in $E$ .

Note that the strongly connected components of $D^T$ are exactly the same as the strongly connected components of $D$ .

Steps of the algorithm:

Perform a DFS in $D$ take note of the postorder of the vertices
Create the transpose graph $D^T$
Perform a DFS in $D^T$ according to the reverse postorder of the vertices

Example: Starting the DFS at $c$ visiting $d$ and $e$ and then $a$ and $b$ and finally restarting the DFS at $f$ (because we cannot reach it from $c$ ) gives the following result. The number at each vertex indicates the postorder, the DFS edges are marked in red.

Keeping the postorder in mind, we now create the transposed graph $D^T$ .

On the resulting graph $D^T$ we now perform a DFS starting at the vertex with the highest postorder (here $f$ ). Whenever we restart the DFS, we begin a new strongly connected component. Again the DFS edges are indicated in red.

Implementation

Implementation in C++:

struct graph
{
  int n;
  int num_comp = 0;
  vector<vector<int>> adjlist;
  vector<int> post;
  vector<int> comp;


  void dfs(int curr, int curr_comp = -2)
  {
      if (comp[curr] != -1) return;
      comp[curr] = curr_comp;
      for (auto nx : adjlist[curr]) dfs(nx, curr_comp);
      post.push_back(curr);
  }

  void kosaraju()
  {
      // Create list of vertices in post order
      comp.assign(n, -1);
      for (int i = 0; i < n; i++) dfs(i);

      // Reverse post order
      reverse(post.begin(), post.end());

      // Build transpose graph
      vector<vector<int>> rev(n);
      for (int i = 0; i < n; i++)
              for (auto j : adjlist[i]) rev[j].push_back(i);

      swap(rev, adjlist);

      // Run dfs in reverse post order on transpose graph
      comp.assign(n, -1);
      for (int i = 0; i < n; i++)
              if (comp[post[i]] == -1) dfs(post[i], num_comp++);

      // Restore original graph
      swap(rev, adjlist);
  }
};

Remark In the end we have a vector comp such that for any vertex $v$ we have that $v$ belongs to the strongly connected component comp[v]. We can now build the component graph in $O(E)$ by iterating over all edges of $D$ and for an edge $(u,v)\in E(D)$ adding the edge (comp[u],comp[v]) to the component graph if it is not contained already.