Graph Theory37 sections · 1633 units
Open in Course

Kosaraju Example

(4-node directed graph)

We trace Kosaraju on this graph: 1→2→3→11 \to 2 \to 3 \to 1, 3→43 \to 4. First DFS starting from 11: visit 11, then 22, then 33, then 44. Finish order (pushed to stack): [4,3,2,1][4, 3, 2, 1] (stack top is 11). Transpose graph: 1←2←3←11 \leftarrow 2 \leftarrow 3 \leftarrow 1, 3←43 \leftarrow 4.

Second DFS: pop 11, explore {1,2,3}\{1, 2, 3\} (one SCC). Pop 44, explore {4}\{4\} (another SCC). Result: Two SCCs found: {1,2,3}\{1, 2, 3\} and {4}\{4\}.