The Kosaraju–Sharir algorithm is a graph algorithm that partitions a directed graph into its strongly connected components: maximal sets of vertices in which every vertex can reach every other by following directed edges. It performs two passes of depth-first search (DFS), one on the original graph and one on the graph with all edges reversed. The order established by the first pass ensures that each search tree in the second pass identifies exactly one component. For a graph represented by adjacency lists, its running time is .
Problem and terminology
Let be a finite directed graph, where is the vertex set and is the edge set. Two vertices and belong to the same strongly connected component if both of the following hold:
- There is a directed path from to .
- There is a directed path from to .
Paths of length zero are allowed, so every vertex belongs to a component, including an isolated vertex. Mutual reachability is an equivalence relation, and the components therefore form a unique partition of .
The transpose graph, written , has the same vertices as , with every edge reversed:
Transposing a graph preserves its strongly connected components: reversing paths exchanges the two reachability conditions without changing which pairs satisfy both.
The algorithm is named after S. Rao Kosaraju and Micha Sharir. Its defining feature is the use of DFS finishing order to coordinate two graph traversals.
Algorithm
There are two symmetric versions of the algorithm. One searches first and second; the other searches first and second. Both are correct, provided that the second pass processes vertices in decreasing finishing-time order from the first pass.
The following description uses first.
First pass: record finishing order
Run a complete DFS on , starting a new search from any unvisited vertex whenever necessary. When the search finishes exploring all outgoing edges of a vertex, append that vertex to a list.
This produces vertices in increasing order of DFS finishing time. Reading the list backward gives decreasing finishing-time order, also called reverse postorder.
The list must record completion, not discovery. A vertex is appended only after all recursive searches initiated from it have returned.
Second pass: collect components
Reset the visited state, then scan vertices in reverse order of the finishing list. Whenever an unvisited vertex is encountered, start a DFS from it in .
Every previously unvisited vertex reached by that search belongs to one strongly connected component. Assign all such vertices the same component identifier, then continue scanning the list.
The second pass maintains one global visited or component-label array. Vertices assigned to an earlier component are not explored again.
Pseudocode
The following pseudocode uses recursive DFS and integer component identifiers:
KosarajuSharir(G):
GT = transpose(G)
visited = array indexed by vertices, initially false
finish = empty list
procedure FirstDFS(v):
visited[v] = true
for each w in G.out_neighbors(v):
if not visited[w]:
FirstDFS(w)
finish.append(v)
for each vertex v in G:
if not visited[v]:
FirstDFS(v)
component = array indexed by vertices, initially UNASSIGNED
count = 0
procedure SecondDFS(v, id):
component[v] = id
for each w in GT.out_neighbors(v):
if component[w] == UNASSIGNED:
SecondDFS(w, id)
for each v in reverse(finish):
if component[v] == UNASSIGNED:
SecondDFS(v, count)
count = count + 1
return component, count
For any two vertices and , equality of their returned component identifiers means that they are mutually reachable. The numerical identifiers themselves are not unique: they can depend on vertex and adjacency-list iteration order.
Why it works
The condensation graph
Contract each strongly connected component into a single vertex, retaining edges between distinct components. The resulting condensation graph is a directed acyclic graph (DAG).
It cannot contain a directed cycle: components on such a cycle would all be mutually reachable and would therefore constitute one larger strongly connected component.
The algorithm effectively uses finishing times to arrange these component vertices in a topological order, without knowing the components in advance.
The finishing-time property
Let be the finishing time of vertex in the first DFS pass. For a component , define
If there is an edge from a component to a distinct component , then
To see why, consider which component is discovered first:
- If is discovered first, its DFS can reach all vertices of and, through the intercomponent edge, all vertices of . These vertices finish before the DFS call at the first-discovered vertex in finishes.
- If is discovered first, its search cannot reach , because an edge from to together with a path back would place them in the same component. The search through therefore finishes before is discovered.
Thus, the maximum finishing times decrease along every edge between distinct components.
Why each second-pass search finds exactly one component
The component containing the unassigned vertex with greatest finishing time has no incoming edge from another unassigned component in . Such an incoming edge would contradict the finishing-time inequality.
After transposition, that component has no outgoing edge to another unassigned component. A search in therefore cannot leave it for an unassigned component. At the same time, transposition preserves strong connectivity, so the search reaches every vertex within it.
After this component is labeled, the same argument applies to the remaining unassigned components. Repeating the process finds the entire partition.
This reasoning does not imply that every vertex of one component finishes before every vertex of another. It is the maximum finishing time of each component that provides the necessary ordering.
Example
Consider a graph with edges
Its strongly connected components are
The condensation graph is a chain:
A first-pass DFS beginning at , with neighbors explored in the order implied by the displayed edges, can produce the finishing list
The second pass reads this list backward and searches the transpose:
- Starting at , it reaches and .
- Starting at the next unassigned vertex, , it reaches and . Any edges to the already assigned component are ignored.
- Starting at , it collects only .
With this orientation of the two passes, components are discovered in topological order of the original condensation graph. Searching first and second produces the reverse component order.
Complexity and implementation
With an adjacency-list representation, building the transpose takes time. Each DFS pass visits every vertex once and examines every edge once. The overall time complexity is therefore
The auxiliary space complexity depends on graph storage:
- Visited state, component labels, the finishing list, and the DFS stack require space.
- Materializing a separate transpose requires additional space.
- If incoming and outgoing adjacency lists already exist, or a reverse view is available, the traversal requires only auxiliary space beyond the graph representation.
For an adjacency-matrix representation, enumerating neighbors typically makes the running time .
Recursive and iterative implementations
A recursive implementation is compact, but a DFS tree may have depth . On large or path-like graphs, this can exceed the available call stack.
An iterative implementation can use an explicit stack. The first pass must preserve true DFS finishing order, usually by storing a frame containing a vertex and its next unexplored neighbor, or by using explicit entry and exit events. Merely recording vertices when first pushed does not compute the required order.
In the second pass, only reachability within the unassigned subgraph matters. DFS can therefore be replaced by breadth-first search without changing the resulting components.
Common implementation errors
Typical errors include:
- Recording discovery order instead of finishing order.
- Reading the finishing list forward rather than backward.
- Using the same edge orientation in both passes.
- Failing to reset visited state between passes.
- Starting the first pass from only one vertex, leaving unreachable regions unprocessed.
- Clearing second-pass visited state between components, allowing already assigned vertices to be collected again.
Self-loops and parallel edges do not require special treatment for correctness, although parallel edges increase the number of edge examinations.
Applications and related algorithms
Strongly connected components expose mutually dependent regions in directed systems. Applications include grouping recursive dependencies in a compiler, organizing state graphs in model checking, and reducing a graph to its acyclic condensation for subsequent processing. Component labels answer mutual-reachability queries directly, but they do not by themselves answer arbitrary one-way reachability queries.
The algorithm also supports solving 2-satisfiability through an implication graph: a formula is unsatisfiable exactly when some variable and its negation belong to the same strongly connected component.
Tarjan's strongly connected components algorithm solves the same problem in time using one DFS pass, an active-vertex stack, and low-link values. Unlike the standard Kosaraju–Sharir implementation, it does not need a separate transpose. The two-pass method instead offers a direct separation between computing an ordering and extracting components.
Kosaraju–Sharir is a static-graph algorithm: it computes components for a fixed graph. Maintaining components efficiently as edges are inserted or deleted requires dynamic algorithms rather than simply retaining the original finishing order.