Course contentsShow
← Computer Science
Lesson 735 of 2,87217. Graph Traversal AlgorithmsFree lesson

Kosaraju's Algorithm for SCCs

Find strongly connected components using two DFS passes: one on original graph, one on transpose graph.

Kosaraju's Algorithm for SCCs

What You'll Learn

You'll learn how to find all strongly connected components in a directed graph using two clever DFS passes.

The Core Idea

Kosaraju's Algorithm finds strongly connected components (SCCs) by performing two separate depth-first searches: one on the original graph to determine a special ordering, and another on the transpose graph (where all edges are reversed) using that ordering.

Think of it like identifying friend circles in a social network where friendships are one-way. You first explore everyone to see who influences whom, then reverse all the relationships and explore again in a specific order—groups that stay together in both passes are true mutual circles.

How It Works

Pass 1: Run DFS on the original graph and record the finish times (when each vertex completes). This gives you an ordering that respects the "flow" of edges.

Pass 2: Transpose the graph (reverse every edge). Now run DFS again, but process vertices in decreasing order of their finish times from Pass 1. Each DFS tree you get in this second pass is one SCC.

Why This Works

The key insight: if you start from a vertex in a "sink" SCC (one with no outgoing edges to other SCCs) in the transpose graph, DFS will only reach vertices within that same SCC. Processing by decreasing finish time ensures you always start from such sink components first.

Example Flow

  1. Original graph: run DFS, note finish order
  2. Reverse all edges → transpose graph
  3. Run DFS on transpose in finish-time order
  4. Each DFS tree = one SCC

Key Takeaway: Kosaraju's Algorithm finds strongly connected components using two DFS passes—one on the original graph to get finish times, and one on the transpose graph in reverse finish order to extract SCCs.