A tutorial on the Kosaraju algorithm for strongly connected components

A directed graph contains vertices joined by one-way edges. Two vertices belong to the same strongly connected component, or SCC, when each can reach the other by following directed edges. The output of Kosaraju’s algorithm is a partition of all vertices into these mutually reachable groups. It runs in linear time, making it ideal for exposing circular dependencies, tightly coupled services or closed groups of routes.

Think of a transport graph for scheduled one-way services between Sydney, Melbourne, Brisbane, Adelaide and Perth. If travellers can move from A to B and B back to A through valid connections, those stops form one SCC. Isolated stops and one-way-only services belong elsewhere. The same model suits software imports, task dependencies and state transitions, where identifying groups that can influence one another is more useful than merely listing every reachable node.

The method uses two depth-first search passes: one on the original graph to record finishing order, then one on the reversed graph to collect components. The implementation below uses Python and an explicit stack, avoiding recursion-depth problems on large graphs. Although DFS order is fixed rather than learned, the community’s long short-term memory networks guide offers a useful contrast with sequence models that learn dependencies across ordered data.

Understand strongly connected components

An SCC is about mutual reachability, not visual closeness. Suppose service A calls B, B calls C, and C calls A. All three are mutually reachable, so they form one component even when each also has edges elsewhere. A vertex with no return path to itself is separate, while an isolated vertex is a valid one-member SCC because a zero-length path reaches itself.

The word strongly matters when edges have direction. If a route can travel only from Adelaide to Perth but not back, those cities are not strongly connected; they may still be weakly connected when direction is ignored. Kosaraju preserves direction during both passes, so it distinguishes a dependency cycle from a simple one-way dependency.

Contracting each SCC into one vertex creates the condensation graph. This graph is acyclic: any cycle among components would mean their members could reach one another and should have been one component. In other words, the condensation graph is a directed acyclic graph, or DAG. Its component-level topological ordering is the key insight behind the algorithm, because Kosaraju discovers entire SCCs one at a time rather than testing every pair of vertices.

Prepare the graph and its transpose

Store the graph with an adjacency list, where graph[u] contains the outgoing neighbours of u. For a firmer grasp of adjacency lists and related structures, the site’s core graph data structures guide explains the containers commonly used for graphs. Kosaraju also needs the transpose, usually called the reversed graph: every edge u → v becomes v → u, while self-loops remain in place.

The transpose is not a copy with each list reversed. It changes the direction of every edge because mutual reachability is symmetric: if u reaches v in the original graph, v reaches u in the transpose. Build it with one pass over all vertices and edges, then keep the original graph for the first search and the transpose for the second.

transpose = [[] for _ in range(n)]

for u, neighbours in enumerate(graph):
    for v in neighbours:
        transpose[v].append(u)

This construction scales well because it touches each edge once. In an Australian energy-market model, for example, generators and interconnectors across the National Electricity Market in the eastern states could form a directed graph; reversing those links helps an analyst identify assets that are inseparable under the chosen flow model. The exact market network changes, but the representation and transformation do not.

Record DFS finishing order

The first pass performs DFS over every vertex and edge of the original graph. A vertex is marked visited when first discovered, but its finishing time is recorded only after all reachable descendants have been processed. This finishing order is not the order in which vertices are discovered. It encodes which traversal remained active when another part of the graph was explored, information the second pass will use.

Conceptually, the recursive form is tiny:

dfs(u):
    visited[u] = true
    for each v in graph[u]:
        if not visited[v]:
            dfs(v)
    finish_order.append(u)

Run DFS from every still-unvisited vertex, appending each vertex to one shared finishing-order list. Recursive DFS is elegant, but Python’s recursion limit can be reached on a long chain. The full implementation therefore uses an explicit stack whose entries store a vertex and the index of its next outgoing edge. That preserves true DFS completion order without risking a RecursionError.

Find components on the reversed graph

The second pass runs DFS on the transpose. Pop vertices from the finishing list in reverse order; whenever an unvisited vertex appears, traverse the transpose from it and collect every reached vertex as one SCC. Start another traversal only after that component is complete. The traversal follows reversed edges, but membership within the resulting component is the same as in the original graph because reversing all edges preserves mutual reachability.

Here is a complete iterative implementation. It assumes vertices are the integers 0 through n - 1 and that graph[u] is the list of outgoing neighbours of u.

def kosaraju_scc(graph):
    """Return the strongly connected components of an adjacency-list graph."""
    n = len(graph)

    # Build the transpose: reverse every directed edge.
    transpose = [[] for _ in range(n)]
    for u, neighbours in enumerate(graph):
        for v in neighbours:
            transpose[v].append(u)

    # First pass: record DFS finishing order in the original graph.
    visited = [False] * n
    finish_order = []

    for start in range(n):
        if visited[start]:
            continue

        visited[start] = True
        stack = [(start, 0)]

        while stack:
            u, edge_index = stack[-1]

            if edge_index == len(graph[u]):
                finish_order.append(u)
                stack.pop()
                continue

            v = graph[u][edge_index]
            stack[-1] = (u, edge_index + 1)

            if not visited[v]:
                visited[v] = True
                stack.append((v, 0))

    # Second pass: traverse the transpose in decreasing finishing order.
    visited = [False] * n
    components = []

    for start in reversed(finish_order):
        if visited[start]:
            continue

        component = []
        stack = [start]
        visited[start] = True

        while stack:
            u = stack.pop()
            component.append(u)

            for v in transpose[u]:
                if not visited[v]:
                    visited[v] = True
                    stack.append(v)

        components.append(component)

    return components

For graph = [[1, 2], [0], [0, 3], [4], [3]], the components are {0, 1, 2} and {3, 4}. Vertices 0, 1 and 2 can reach one another, while 3 and 4 form a separate mutual pair. The edge from 2 to 3 connects the groups but does not merge them, because there is no path from 3 or 4 back to the first group.

Why does the traversal collect exactly one SCC? The condensation graph is a DAG, and the DFS finishing order guarantees that the next unprocessed component chosen in reverse finishing order is a source among the remaining components. In the transpose, that source becomes a sink, so DFS cannot leave it for another unprocessed component. Every edge within the SCC is still present, so the traversal reaches all and only its members. Repeating the process partitions the graph.

Implement, analyse, and apply Kosaraju’s algorithm

Kosaraju’s algorithm uses O(V + E) time: each DFS pass visits every vertex and examines every edge a constant number of times. The transpose needs O(V + E) space, while the visited arrays, finishing list, component lists and explicit stacks require O(V) additional space. Consequently, the complete method remains O(V + E) in space and is practical for large directed graphs.

Several properties are worth keeping in view:

• Finishing time means all descendants are processed, not merely that a vertex has been discovered.
• Reversing every edge preserves SCC membership, even though it changes individual paths.
• Separate components may still be joined by one-way edges between them.
• The order of vertices inside one returned component is not significant; the set is.

The approach also maps neatly to common Australian project settings:

• Release and dependency planning for engineering teams working across Australian cities.
• Transport, utility and infrastructure graphs that connect cities and regions.
• Auditable workflows for banks such as ANZ and Commonwealth Bank, as well as federal agencies in Canberra.
• Operational analysis spanning Sydney and Perth, where UTC-normalised timestamps must handle their different daylight-saving rules.
• Import, call and service graphs where mutual dependencies need clear ownership.

Many Australian teams use terms such as “keen” and may hold an arvo design review, and a labelled partition gives such a meeting a concrete artefact. Large employers and government teams also need algorithms whose behaviour and cost can be explained during procurement and resilience reviews. Kosaraju is language-agnostic, but documented assumptions, deterministic tests and clear component lists are what make its output dependable in production.