Kosaraju's Algorithm
Last Updated: May 30, 2026
A Strongly Connected Component (SCC) is a group of vertices in a directed graph where every vertex can reach every other vertex by following directed edges. The 2000 "Bowtie Model" study of the web found that around 30% of all indexed pages belong to one giant SCC, with the rest forming clusters that can reach it or be reached from it but not both.
SCCs appear in social network analysis (groups of people who all follow each other), compiler optimization (cycles in function call graphs), and 2-SAT solvers. They are also a common topic in graph interview questions.
Kosaraju's algorithm finds all SCCs in a directed graph with two passes of DFS. It is conceptually simpler than Tarjan's algorithm and a good way to build intuition for how DFS finish times encode the structure of a directed graph.