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

Kosaraju's algorithm

Kosaraju's algorithm finds the strongly connected components of a directed graph in linear time using two graph traversals and reversed edges.

19 keywords1 linked from5 not yet writtenWritten by AI
AlgorithmStrongly Connect…Directed GraphDepth-first Sear…Adjacency ListDirected acyclic…Breadth-First Se…PseudocodeKosaraju's…

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 O(∣V∣+∣E∣)O(|V|+|E|), where VV is the vertex set and EE 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 G=(V,E)G=(V,E), two vertices uu and vv are mutually reachable if there is a directed path from uu to vv and a directed path from vv to uu. 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 GTG^{T} has the same vertices as GG, but every edge (u,v)(u,v) is replaced by (v,u)(v,u). 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 GG, then searches GTG^{T}.

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 GTG^{T}, 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 GTG^{T}, 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 GTG^{T}, then searches GG 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 f(v)f(v) be the first-pass DFS finishing time of vertex vv. For a component CC, define

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

If the original graph has 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, DFS can reach all of CC and then reach DD. The first-discovered vertex in CC finishes only after all vertices in DD have finished.
  • If DD is discovered first, DFS from DD cannot reach CC. Otherwise, the edge from CC to DD would make the two components mutually reachable. Consequently, all vertices in DD finish before CC is discovered.

Thus decreasing F(C)F(C) 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:

  1. reaches every vertex in its own component, because edge reversal preserves strong connectivity;
  2. 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 GG, the components are output in a topological order of the original condensation graph. Searching GTG^{T} first instead produces the reverse orientation of this component order.

Example

Consider a graph with edges

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

Its SCCs are

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

Their condensation graph is the chain

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

Suppose the first DFS starts at aa and follows the edges along the chain before returning. One possible finishing list is

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

The second pass therefore considers vertices in the order

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

In the transpose graph, the search from aa reaches exactly {a,b,c}\{a,b,c\}. The next unassigned starting vertex, dd, yields {d,e}\{d,e\}. Finally, ff 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

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

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 O(∣V∣)O(|V|) auxiliary space.
  • Explicitly storing the transpose requires another O(∣V∣+∣E∣)O(|V|+|E|) 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 O(∣V∣2)O(|V|^2), rather than linear in the number of edges.

Iterative DFS

Recursive implementations can require recursion depth proportional to ∣V∣|V|, 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 O(∣V∣+∣E∣)O(|V|+|E|) 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.