Graph Theory37 sections · 1633 units
Open in Course

Kosaraju Example

(4-node directed graph)

We trace Kosaraju on this graph: 12311 \to 2 \to 3 \to 1, 343 \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: 12311 \leftarrow 2 \leftarrow 3 \leftarrow 1, 343 \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\}.