Graph Algorithms • Connectivity

Kosaraju's Algorithm

A two-pass DFS approach to find all Strongly Connected Components. It utilizes a transpose graph to ensure that DFS traversal is trapped within single SCCs.

Try Interactive Simulator

Pass 1: Stack

Perform DFS on the original graph. Push nodes onto a stack in order of their finishing times.

Transpose

Reverse every directed edge in the graph. SCCs remain SCCs, but the inter-component reachability is reversed.

Pass 2: Extract

Pop nodes from the stack and perform DFS on the reversed graph. Each DFS call extracts one full SCC.

Connectivity

In an SCC, every vertex is reachable from every other vertex. Kosaraju's is the classic way to find these components.

Loading Lab...

Graph Algorithms • Connectivity

Kosaraju's Algorithm

A two-pass DFS approach to find all Strongly Connected Components. It utilizes a transpose graph to ensure that DFS traversal is trapped within single SCCs.

Try Interactive Simulator

Pass 1: Stack

Perform DFS on the original graph. Push nodes onto a stack in order of their finishing times.

Transpose

Reverse every directed edge in the graph. SCCs remain SCCs, but the inter-component reachability is reversed.

Pass 2: Extract

Pop nodes from the stack and perform DFS on the reversed graph. Each DFS call extracts one full SCC.

Connectivity

In an SCC, every vertex is reachable from every other vertex. Kosaraju's is the classic way to find these components.

Scc Kosaraju

Scc Kosaraju

Kosaraju's Algorithm

Pass 1: Stack

Transpose

Pass 2: Extract

Connectivity

Kosaraju's Algorithm

Pass 1: Stack

Transpose

Pass 2: Extract

Connectivity