Visualizer CodeViz · Algorithms, visualized

Part II · Directed graphs · week 2

Strong components (Kosaraju–Sharir)

Reverse the digraph, take its reverse postorder, then DFS the original in that order. Each tree you get is a strong component — and nobody finds the proof obvious.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

timeO(V + E)
passes2 depth-first searches
queryO(1) after preprocessing
definitionv and w each reach the other

Reference: Sedgewick & Wayne, §4.2; Kosaraju 1978, Sharir 1981.

Strong components (Kosaraju–Sharir) in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class KosarajuSCC:
    # v and w are STRONGLY connected when v can reach w AND w can reach v.
    # Pass 1: reverse postorder of the REVERSED digraph.
    # Pass 2: DFS the original digraph in that order; each tree is one
    #         strong component. (Correct, and famously unobvious.)

    def __init__(self, digraph):
        order = Topological(digraph.reverse()).order      # pass 1
        self.marked = [False] * digraph.V
        self.id = [-1] * digraph.V
        self.count = 0
        for v in order:                                  # pass 2
            if not self.marked[v]:
                self._dfs(digraph, v)
                self.count += 1

    def _dfs(self, digraph, v):
        self.marked[v] = True
        self.id[v] = self.count
        for w in digraph.adj(v):
            if not self.marked[w]:
                self._dfs(digraph, w)

    def strongly_connected(self, v, w):
        return self.id[v] == self.id[w]

Why it works

What the two passes do

Pass 1 computes the reverse postorder of the reversed digraph. Think of it as sorting the vertices so that the “source-most” strong components come first. Pass 2 then runs an ordinary DFS on the original digraph in that order, and because of how the order was built, each search is trapped inside one strong component: it can reach everything in that component and nothing outside it that has not already been claimed.

Sedgewick's own comment stands: the algorithm is remarkably simple and the proof is not obvious. It is worth accepting the proof on trust the first time and instead watching which vertex starts each pass-2 search — that choice is doing all the work.

Strong connectivity is an equivalence relation

Reflexive, symmetric, transitive — so the vertices split cleanly into components, exactly as with undirected connectivity. Contract each component to a single vertex and the result is the kernel DAG, always acyclic (a cycle between two components would merge them). That is how you reason about a cyclic dependency graph: find the strong components, then topologically sort what is left.

Why not just DFS from every vertex

The naive check — for each pair, can v reach w and w reach v? — costs O(V(V + E)). Kosaraju–Sharir gets the same answer in two passes. Historically this was surprising: the linear-time algorithm arrived (Tarjan, 1972; Kosaraju–Sharir later, with a much simpler argument) decades after the problem was posed.

Where it is used

Ecological food webs (which species form a cycle of dependency), web page communities, dataflow and pointer analysis in compilers, and 2-satisfiability — 2-SAT is solvable in linear time precisely by computing strong components of the implication graph.

What to try in the animation

The default has strong components {0,1,2}, {3,4,5}, {6}, {7}. The tinyDG preset is the course's example with five.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Strong components (Kosaraju–Sharir) in the player →

The rest of Directed graphs