Algorithm catalog

Graph algorithms / interactive lesson

Tarjan's Strongly Connected Components Algorithm

Find strongly connected components in one DFS using discovery indices, lowlink values, and a stack of unfinished vertices.

University Guided lesson
Strongly connected components

Tarjan

Step 1 / 33Original graph
Ai:- l:-Bi:- l:-Ci:- l:-Di:- l:-Ei:- l:-Fi:- l:-Gi:- l:-Hi:- l:-

About the algorithm

Tarjan's algorithm finds strongly connected components in one depth-first search. It assigns every vertex an index, keeps live vertices on a stack, and uses lowlink values to detect exactly when a complete SCC can be popped.

Index and lowlink

The index is the DFS discovery time. Lowlink is the smallest discovery index reachable from the vertex through DFS-tree edges and then possibly one edge to a vertex that is still on the stack.

Stack invariant

Only unfinished vertices stay on the stack. An edge to a vertex that has already been popped points into a completed component and must not lower the current lowlink.

Root test

When lowlink(v) equals index(v), v is the oldest reachable live vertex in that DFS region. Popping the stack up to v yields one whole strongly connected component.

Code companion

Connect each visual decision to an implementation pattern.

index = 0
stack = empty stack

strongconnect(v):
  v.index = index
  v.lowlink = index
  index += 1
  stack.push(v)

  for w in v.out_neighbors:
    if w.index is undefined:
      strongconnect(w)
      v.lowlink = min(v.lowlink, w.lowlink)
    else if w is on stack:
      v.lowlink = min(v.lowlink, w.index)

  if v.lowlink == v.index:
    pop vertices through v as one SCC