Kosaraju's algorithm is an algorithm for finding the strongly connected components of a directed graph. It performs two graph traversals: the first determines an order based on depth-first search finishing times, and the second explores the graph with every edge reversed. With an adjacency-list representation, its running time is , where is the vertex set and is the edge set. It is also known as the Kosaraju–Sharir algorithm, reflecting its attribution to S. Rao Kosaraju and Micha Sharir.
Problem and definitions
In a directed graph , two vertices and are mutually reachable if there is a directed path from to and a directed path from to . Mutual reachability partitions the vertices into strongly connected components, commonly abbreviated SCCs.
Each SCC is maximal: no additional vertex can be included while preserving mutual reachability among all vertices in the component. Every vertex belongs to exactly one SCC. A single vertex may form a component even when it has no self-loop, because a path of length zero connects a vertex to itself.
Two related constructions explain the algorithm:
- The transpose graph has the same vertices as , but every edge is replaced by . Reversing all edges preserves the SCCs.
- The condensation graph replaces each SCC with one vertex and retains edges between distinct components. It is a directed acyclic graph: a cycle among distinct components would make them mutually reachable, so they would actually form one component.
The goal is to assign each vertex a component identifier, or equivalently to output the sets of vertices forming the SCCs.
Algorithm
One standard version first searches , then searches .
First pass: record finishing order
Run depth-first search over the entire original graph. Whenever a search finishes processing a vertex—that is, after all of its outgoing neighbors have been examined—append that vertex to a list.
The outer search must consider every vertex, starting a new DFS whenever an unvisited vertex is encountered. A single DFS from an arbitrary starting point need not reach the whole graph.
Appending vertices when they finish produces increasing finishing-time order. Reading the list backward gives decreasing finishing-time order, often called reverse postorder.
Reverse the graph
Construct , or provide access to the incoming neighbors of each vertex.
This step may be performed before the first pass; only the orientation used by each traversal matters.
Second pass: extract components
Clear the visited state. Consider vertices in decreasing first-pass finishing time. Whenever an unvisited vertex is encountered, start a search from it in , visiting only vertices not already assigned to a component.
All vertices newly reached by that search form one SCC. Give them the same component identifier, then continue through the ordering.
The second traversal is conventionally another DFS, but breadth-first search also works: the finishing-time requirement applies to the first pass, whereas the second pass only needs to collect reachable, unassigned vertices.
Pseudocode
The following pseudocode uses recursive DFS in both passes:
kosaraju(G):
visited = empty set
finish_order = empty list
visit_first(v):
add v to visited
for each w in outgoing_neighbors(G, v):
if w not in visited:
visit_first(w)
append v to finish_order
for each vertex v in G:
if v not in visited:
visit_first(v)
GT = transpose(G)
component = empty mapping
component_count = 0
visit_second(v, id):
component[v] = id
for each w in outgoing_neighbors(GT, v):
if w not in component:
visit_second(w, id)
for each v in reverse(finish_order):
if v not in component:
visit_second(v, component_count)
component_count = component_count + 1
return component
A symmetric variant first searches , then searches in decreasing finishing time from that first pass. Both variants are correct, but their edge orientations and processing orders must remain consistent.
Why it works
The key property concerns finishing times of whole components, not necessarily the relative finishing times of every pair of vertices in different components.
Let be the first-pass DFS finishing time of vertex . For a component , define
If the original graph has an edge from a component to a distinct component , then
To see why, consider which component is discovered first:
- If is discovered first, DFS can reach all of and then reach . The first-discovered vertex in finishes only after all vertices in have finished.
- If is discovered first, DFS from cannot reach . Otherwise, the edge from to would make the two components mutually reachable. Consequently, all vertices in finish before is discovered.
Thus decreasing gives a topological ordering of the original condensation graph.
The second pass starts with a component having no incoming edge from any still-unassigned component in the original graph. In the transpose, it therefore has no outgoing edge to another still-unassigned component. A search from it:
- reaches every vertex in its own component, because edge reversal preserves strong connectivity;
- cannot enter a different unassigned component.
The search consequently extracts exactly one SCC. Applying the same argument after each extracted component proves correctness for the entire graph.
For the version that first searches , the components are output in a topological order of the original condensation graph. Searching first instead produces the reverse orientation of this component order.
Example
Consider a graph with edges
Its SCCs are
Their condensation graph is the chain
Suppose the first DFS starts at and follows the edges along the chain before returning. One possible finishing list is
The second pass therefore considers vertices in the order
In the transpose graph, the search from reaches exactly . The next unassigned starting vertex, , yields . Finally, forms its own component.
Different vertex and neighbor iteration orders can change the finishing list and the numerical component labels. They do not change the partition into SCCs.
Complexity and implementation
With adjacency lists, each DFS examines every vertex and every edge at most a constant number of times. Constructing the transpose also takes linear time. The overall time complexity is therefore
The space complexity depends on the graph representation and on what storage is counted:
- Visited flags, component labels, the finishing list, and traversal state require auxiliary space.
- Explicitly storing the transpose requires another space.
- If incoming and outgoing adjacency lists already exist, the algorithm can use them directly without creating a separate transpose.
With an adjacency matrix and straightforward row scans, the running time is , rather than linear in the number of edges.
Iterative DFS
Recursive implementations can require recursion depth proportional to , potentially exhausting the call stack on long paths. An iterative implementation can use an explicit stack, but must preserve DFS finishing events in the first pass.
Simply recording vertices when they are first pushed or discovered is not sufficient. Common implementations use stack frames that retain the next neighbor to examine, or separate entry and exit events. A vertex is appended to the finishing list only after its descendants have been processed.
Other implementation considerations
- The first pass must cover all vertices, including isolated vertices.
- The second pass must use fresh visited state or an initially empty component assignment.
- Self-loops and parallel edges do not affect correctness.
- Component identifiers are labels, not intrinsic properties of the graph.
- An empty graph produces no components.
- The usual implementation assumes the graph remains unchanged throughout both passes; it is not an incremental algorithm for maintaining SCCs under updates.
Applications and related algorithms
SCC decomposition separates cyclic regions of a directed graph from the acyclic relationships between them. Applications include:
- Dependency analysis: mutually dependent modules, tasks, or definitions can be grouped before processing their condensation graph.
- Program analysis: compilers and static-analysis systems can identify cyclic regions of control-flow or dependency graphs for iterative processing.
- Directed reachability: contracting SCCs reduces reachability questions to a smaller acyclic graph, although further processing is needed to answer arbitrary reachability queries efficiently.
- 2-satisfiability: a Boolean formula in 2-CNF is unsatisfiable exactly when some variable and its negation belong to the same SCC of its implication graph.
Kosaraju's algorithm is especially straightforward to explain and verify because it separates finishing-order computation from component extraction. Its principal practical cost is the need to traverse edges in both directions.
Tarjan's strongly connected components algorithm also runs in time, but identifies components during one DFS using discovery indices, low-link values, and a stack. It does not require constructing the transpose. Both algorithms produce the same SCC partition; their traversal bookkeeping, memory requirements, and component output order differ.