Implementing Kosaraju's algorithm for strongly connected components

Directed graphs model dependencies, routes and communication: a build waits for a library, a payment waits for a bank, and a delivery waits for a depot. Strongly connected components, often abbreviated SCCs, reveal groups of vertices in which each vertex can reach every other by following edge directions. They compress mutual dependencies without discarding the behaviour of the original graph.

Kosaraju's algorithm finds these groups with two depth-first searches. The first records when vertices finish exploring; the second visits a transposed graph in reverse finishing order. Its running time is linear in the number of vertices and edges, making it practical for dependency graphs, transport models and large relationship datasets. The implementation also shows why traversal order matters rather than treating graph analysis as a black box.

What strongly connected components reveal

An SCC is maximal: adding another reachable vertex would either place it in the same group or make the group invalid. Mutual reachability defines equivalence classes, so every vertex belongs to exactly one component, including an isolated vertex as a component of one. A directed cycle is one familiar example, but SCCs can contain several vertices whose return paths depend on different intermediate nodes.

Consider an Australian online marketplace with suppliers in Sydney and Melbourne, warehouses in Brisbane and Perth, and a storefront serving Adelaide. Model a supplier-to-warehouse edge as a dependency and a warehouse-to-storefront edge as fulfilment flow. If reverse paths reconnect several participants, they form one SCC. That does not prove the businesses cooperate or conflict; it describes which modelled dependencies are mutually reachable.

Contracting each component produces the condensation graph, a directed acyclic graph, or DAG. Edges between components cannot run both ways, since that would merge them into a larger SCC. This graph-of-components is often the most useful output for dependency management. This community-written style fits the site's open educational approach, described in About hello ML.

How Kosaraju's two-pass search works

The first pass performs DFS on the original graph. A vertex is added to the finish order only after every outgoing edge has been examined and every newly reached neighbour has been handled. This postorder is important: a vertex that finishes early may need to appear later in the second pass. Recording only visit order would lose the boundary information the algorithm depends upon.

The second pass uses the transpose, a graph containing exactly the same vertices but with each edge reversed. Process vertices from the latest finish to the earliest, and run DFS on the transpose from each unvisited vertex. Every vertex reached by that search belongs to one SCC. The finishing order guarantees that the search cannot spill into a different, unprocessed component.

Reversing edges is not the same as ignoring their directions, and the transposed graph is not the condensation graph. It is an auxiliary graph used solely for component discovery. For comparison, A* pathfinding seeks one cost-efficient path using edge weights, whereas SCC detection groups mutually reachable vertices without optimising a route between two endpoints.

Designing adjacency lists for real applications

Store the graph with an adjacency list: each vertex maps to its outgoing neighbours. Build a second adjacency list for the transpose while reading each edge once. In Python, dictionaries provide readable vertex names, while integer indices can reduce memory overhead for very large inputs. The vertex collection must include every endpoint, including isolated vertices, so that no node disappears during either traversal.

Direction matters in everyday Australian transport models. A commuter using Opal in Sydney or myki in Melbourne may travel from a station to a transfer hub, but the permitted reverse journey depends on services and walking links. Representing each permitted movement as a directed edge captures that asymmetry. Mutual reachability then distinguishes truly connected groups from routes that only work in one direction.

Local commerce offers another practical use. A small-business fulfilment dashboard might link customers, stock locations, payment providers and couriers while keeping Australian Privacy Act 1988 obligations in view. Organisations subject to that law should apply relevant OAIC guidance, including data minimisation and security, before joining records into a graph. Refund and consumer-guarantee duties under the Australian Consumer Law remain separate from the SCC calculation.

A reliable Python implementation

The implementation below uses explicit stacks, avoiding Python's recursion limit and the failure mode of losing finish order when a simple visited-marking stack is used. The first stack stores a vertex and the index of its next outgoing edge. That extra index lets the code resume exactly where it left off. The second pass only needs reachability, so an ordinary depth-first stack is sufficient.

def strongly_connected_components(vertices, edges):
    vertices = list(vertices)
    graph = {vertex: [] for vertex in vertices}
    reverse_graph = {vertex: [] for vertex in vertices}

    for source, target in edges:
        graph[source].append(target)
        reverse_graph[target].append(source)

    # First pass: record depth-first finishing order.
    visited = set()
    finish_order = []

    for start in vertices:
        if start in visited:
            continue

        visited.add(start)
        frames = [(start, 0)]

        while frames:
            vertex, edge_index = frames[-1]

            if edge_index == len(graph[vertex]):
                finish_order.append(vertex)
                frames.pop()
                continue

            neighbour = graph[vertex][edge_index]
            frames[-1] = (vertex, edge_index + 1)

            if neighbour not in visited:
                visited.add(neighbour)
                frames.append((neighbour, 0))

    # Second pass: explore the transposed graph backwards
    # through the finishing order.
    seen = set()
    components = []

    for start in reversed(finish_order):
        if start in seen:
            continue

        seen.add(start)
        stack = [start]
        component = []

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

            for neighbour in reverse_graph[vertex]:
                if neighbour not in seen:
                    seen.add(neighbour)
                    stack.append(neighbour)

        components.append(component)

    return components

Pass vertices as a set or list and edges as an iterable of (source, target) pairs. The function returns a list of components, with no guarantee about the order of vertices inside each component. Compare membership rather than list positions when checking results. The transpose is built in the same loop as the original graph, keeping edge processing straightforward.

For example, Brisbane → Sydney → Melbourne → Brisbane forms a mutually reachable cycle, so those three cities belong to one component in that illustrative graph. Perth → Brisbane without a path back leaves Perth in a separate component. These city labels are simply vertex names; they do not imply direct transport or commercial links.

Performance checks and implementation recommendations

Let V be the number of vertices and E the number of edges. Each pass visits every vertex and scans every edge at most once, giving O(V + E) time under standard dictionary assumptions. Adjacency lists and their transpose take O(V + E) space, while the visited sets, finish order and component lists use O(V) additional space.

Small graphs are easy to validate by hand: draw each SCC, then confirm that every edge connects two vertices in the same component. An independent SCC implementation can provide a larger cross-check. Building the condensation graph and testing it for cycles is another useful verification step, since condensation of a valid SCC partition must be acyclic.

These checks reduce subtle implementation errors:

• Include every endpoint and isolated vertex in the vertex collection, so both traversals see the complete graph.
• Keep edge direction explicit when constructing the transpose; reversing every edge once is the required operation.
• Trace the first traversal's finish order on a small cycle to confirm that postorder, not visit order, is recorded.
• Test self-loops, parallel edges, disconnected graphs and long directed chains before scaling up.
• Use stable, non-sensitive identifiers in diagnostic output, especially when production data includes customer records.

An SCC identifies mutual reachability, not whether the relationships it represents are desirable or harmful. That distinction keeps cycle detection, graph compression and dependency analysis technically precise without assigning a business meaning that the graph never established.