Find Strongly Connected Components in a Directed Graph

External

• https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/rng2S/computing-strong-components-the-algorithm
• https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/QFOFt/computing-strong-components-the-analysis

Internal

• Directed Graph Connectivity
• Graph Search | Depth-First Search

Overview

Finding strongly connected components in a directed graph is a form of clustering heuristics: strongly connected components represent clusters where the objects represented by the vertices are clustered in some way.

Strongly connected components of a directed graph can be computed with Kosaraju's Two-Pass algorithm, which consists of two passes of depth-first search.

Kosaraju's Two-Pass Algorithm

The algorithm has three steps:

1. Reverse all of the arcs of the given graph. Let G^rev = G with all arcs revered.

2. Do the first depth-first search pass on the reversed graph. The practical implementation should run DFS on the original graph G but going in the opposite direction of the arcs, backwards.

3.