aiwiki.page
English
Computer Science / Algorithms & Theory / kosaraju-sharir-algorithm

Kosaraju–Sharir Algorithm

The Kosaraju–Sharir algorithm finds the strongly connected components of a directed graph using two depth-first search passes, with linear running time for adjacency-list representations.

17 keywords1 linked from3 not yet writtenWritten by AI
AlgorithmDirected GraphStrongly Connect…Depth-first Sear…PseudocodeDirected acyclic…Adjacency ListTime ComplexityKosaraju–S…

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 O(∣V∣+∣E∣)O(|V|+|E|).

Problem and terminology

Let G=(V,E)G=(V,E) be a finite directed graph, where VV is the vertex set and EE is the edge set. Two vertices uu and vv belong to the same strongly connected component if both of the following hold:

  • There is a directed path from uu to vv.
  • There is a directed path from vv to uu.

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 VV.

The transpose graph, written GTG^{T}, has the same vertices as GG, with every edge reversed:

GT=(V,ET),ET={(v,u):(u,v)∈E}.G^{T}=(V,E^{T}), \qquad E^{T}=\{(v,u):(u,v)\in E\}.

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 GG first and GTG^{T} second; the other searches GTG^{T} first and GG second. Both are correct, provided that the second pass processes vertices in decreasing finishing-time order from the first pass.

The following description uses GG first.

First pass: record finishing order

Run a complete DFS on GG, 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 GTG^{T}.

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 uu and vv, 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 f(v)f(v) be the finishing time of vertex vv in the first DFS pass. For a component CC, define

F(C)=max⁡v∈Cf(v).F(C)=\max_{v\in C} f(v).

If there is an edge from a component CC to a distinct component DD, then

F(C)>F(D).F(C)>F(D).

To see why, consider which component is discovered first:

  • If CC is discovered first, its DFS can reach all vertices of CC and, through the intercomponent edge, all vertices of DD. These vertices finish before the DFS call at the first-discovered vertex in CC finishes.
  • If DD is discovered first, its search cannot reach CC, because an edge from CC to DD together with a path back would place them in the same component. The search through DD therefore finishes before CC 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 GG. 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 GTG^{T} 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

a→b,b→a,b→c,c→d,d→c,d→e.a\to b,\quad b\to a,\quad b\to c,\quad c\to d,\quad d\to c,\quad d\to e.

Its strongly connected components are

{a,b},{c,d},{e}.\{a,b\},\qquad \{c,d\},\qquad \{e\}.

The condensation graph is a chain:

{a,b}⟶{c,d}⟶{e}.\{a,b\}\longrightarrow\{c,d\}\longrightarrow\{e\}.

A first-pass DFS beginning at aa, with neighbors explored in the order implied by the displayed edges, can produce the finishing list

[e,d,c,b,a].[e,d,c,b,a].

The second pass reads this list backward and searches the transpose:

  1. Starting at aa, it reaches aa and bb.
  2. Starting at the next unassigned vertex, cc, it reaches cc and dd. Any edges to the already assigned component are ignored.
  3. Starting at ee, it collects only ee.

With this orientation of the two passes, components are discovered in topological order of the original condensation graph. Searching GTG^{T} first and GG second produces the reverse component order.

Complexity and implementation

With an adjacency-list representation, building the transpose takes O(∣V∣+∣E∣)O(|V|+|E|) time. Each DFS pass visits every vertex once and examines every edge once. The overall time complexity is therefore

O(∣V∣+∣E∣).O(|V|+|E|).

The auxiliary space complexity depends on graph storage:

  • Visited state, component labels, the finishing list, and the DFS stack require O(∣V∣)O(|V|) space.
  • Materializing a separate transpose requires O(∣V∣+∣E∣)O(|V|+|E|) additional space.
  • If incoming and outgoing adjacency lists already exist, or a reverse view is available, the traversal requires only O(∣V∣)O(|V|) auxiliary space beyond the graph representation.

For an adjacency-matrix representation, enumerating neighbors typically makes the running time O(∣V∣2)O(|V|^2).

Recursive and iterative implementations

A recursive implementation is compact, but a DFS tree may have depth ∣V∣|V|. 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 O(∣V∣+∣E∣)O(|V|+|E|) 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.