A tutorial on topological sorting for directed graphs

Many real-world systems contain tasks that must happen in a particular order. A software project may require dependencies to be installed before a build can run, a university timetable may depend on prerequisite subjects, and a data pipeline may need cleaning before analysis. A topological sort turns those relationships into a linear sequence.

This algorithm applies to directed acyclic graphs, commonly called DAGs. It is useful because it exposes dependency order, detects impossible cycles, and can be implemented efficiently with either breadth-first or depth-first graph traversal. The examples below use Python, while the underlying ideas apply equally well in C and other programming languages.

What a topological ordering means

A directed graph consists of vertices and directed edges. If an edge goes from A to B, it can represent “A must happen before B”. A topological ordering is a sequence of every vertex in which A appears before B for every edge A → B.

For example, consider these dependencies:

Learn syntax → Build project
Install tools → Build project
Build project → Run tests

A valid ordering could be Learn syntax, Install tools, Build project, Run tests. The first two tasks can be swapped because neither depends on the other. This means a graph can have several valid topological orders.

A topological ordering exists exactly when the directed graph has no cycle. A chain such as A → B → C is acyclic, but adding C → A creates a circular dependency. No sequence can place each vertex before its successor in that cycle, so a sorting algorithm must report failure rather than return an invalid result.

Representing dependencies in code

An adjacency list is usually the best graph representation for topological sorting. Each vertex stores a collection of vertices reachable by its outgoing edges. For a graph containing A → C and B → C, the adjacency list can be written as:

graph = {
    "A": ["C"],
    "B": ["C"],
    "C": []
}

The list of incoming edges, called the indegree of a vertex, is also important for Kahn’s algorithm. Here, C has an indegree of two, while A and B have an indegree of zero. Vertices with zero indegree have no remaining prerequisites and may safely appear next in the output.

When the graph is built from input, include vertices that have no outgoing edges. Omitting an isolated task can cause the result to contain only part of the graph. In production code, it is also worth validating that every referenced dependency is a known vertex, especially when the data comes from a configuration file or a web form.

Kahn’s algorithm step by step

Kahn’s algorithm uses a queue of vertices whose indegree is zero. It repeatedly removes one available vertex, appends it to the ordering, and reduces the indegree of each outgoing neighbour. If a neighbour reaches zero, it enters the queue.

The process is similar to working through a project backlog: begin with tasks that have no prerequisites, complete one, and then unlock any tasks that are now ready. A queue gives a predictable breadth-first style, although a stack or priority queue can be used when a particular tie-breaking rule is needed.

from collections import deque

def topological_sort(graph):
    indegree = {vertex: 0 for vertex in graph}

    for neighbours in graph.values():
        for neighbour in neighbours:
            if neighbour not in indegree:
                indegree[neighbour] = 0
            indegree[neighbour] += 1

    ready = deque(
        vertex for vertex, degree in indegree.items()
        if degree == 0
    )
    ordering = []

    while ready:
        vertex = ready.popleft()
        ordering.append(vertex)

        for neighbour in graph.get(vertex, []):
            indegree[neighbour] -= 1
            if indegree[neighbour] == 0:
                ready.append(neighbour)

    if len(ordering) != len(indegree):
        raise ValueError("The graph contains a cycle")

    return ordering

The len(ordering) check is the cycle detector. If a cycle exists, its vertices never reach indegree zero, so they remain outside the result. The function therefore rejects both a simple loop such as A → B → A and a larger circular dependency.

Depth-first search alternative

A second standard method uses depth-first search, or DFS. During traversal, each vertex has one of three states: unvisited, currently visiting, or completely visited. A directed edge to a currently visiting vertex reveals a back edge and therefore a cycle.

Once DFS finishes exploring a vertex, that vertex is placed on a stack. Reversing the stack produces a topological ordering. The key operation is placing a vertex after all of its descendants have been processed.

def topological_sort_dfs(graph):
    state = {vertex: 0 for vertex in graph}
    result = []

    def visit(vertex):
        if state[vertex] == 1:
            raise ValueError("The graph contains a cycle")
        if state[vertex] == 2:
            return

        state[vertex] = 1

        for neighbour in graph.get(vertex, []):
            if neighbour not in state:
                state[neighbour] = 0
            visit(neighbour)

        state[vertex] = 2
        result.append(vertex)

    for vertex in list(state):
        visit(vertex)

    result.reverse()
    return result

DFS can be elegant when the program already uses recursive graph traversal. However, Python’s recursion limit can become a practical problem for a very long chain, such as thousands of tasks arranged one after another. Kahn’s iterative approach avoids that particular risk and is often easier to connect to a live queue of available work.

Correctness and performance

Kahn’s algorithm is correct because it selects only vertices with no unprocessed incoming edges. When such a vertex is appended, every prerequisite edge leading to it has already been removed or there were no prerequisites to begin with. Removing its outgoing edges can only make additional valid vertices available; it cannot invalidate the existing prefix of the ordering.

If the algorithm stops before processing every vertex, the remaining subgraph has no zero-indegree vertex. In a finite directed graph, that situation implies that following outgoing edges eventually enters a cycle. Thus, the algorithm either returns a valid ordering of all vertices or identifies that no ordering exists.

With an adjacency list, both Kahn’s algorithm and DFS run in O(V + E) time, where V is the number of vertices and E is the number of directed edges. Their auxiliary space is O(V), excluding the graph itself. An adjacency matrix would use O(V²) space, which is wasteful for a sparse dependency graph.

The result is not automatically unique. If several vertices have indegree zero at the same time, any of them may be selected. A min-heap can produce lexicographically smallest output, while a priority queue can enforce a business rule such as processing the earliest due task first. The choice changes the order, not the validity conditions.

From algorithms to working systems

Topological sorting is common in build tools, package managers, spreadsheet recalculation, and workflow engines. A build system can compile libraries before applications that import them. A package manager can install prerequisites first. A spreadsheet can recalculate cells in dependency order, provided the formulas do not contain circular references.

Machine learning workflows also form DAGs: collect data, validate it, transform features, train a model, evaluate it, and publish a result. The broader context is covered in this machine learning guide, where dependency-aware processing connects naturally with reproducible experiments and data pipelines.

The technique is useful in Australian settings as well. A Sydney software team might order services in a deployment pipeline, while a Melbourne transport project could model prerequisite tasks for timetable or infrastructure changes. In an Australian retail or logistics platform, supplier feeds, stock updates, warehouse allocation, and delivery notifications may form a directed workflow. If customer information is involved, the design also needs to account for the Australian Privacy Act 1988 and the Australian Privacy Principles; an ordering algorithm does not remove obligations around collection, storage, and disclosure.

Topological sorting is part of a wider group of graph and search techniques. For a different search pattern, see this ternary search tutorial. For compact membership checks in large pipelines, a Bloom filter explanation provides a useful contrast: Bloom filters trade exactness for space efficiency, whereas topological sorting must preserve exact dependency constraints.

Testing and common implementation mistakes

A small acyclic graph is a good starting test. Include a graph with one chain, a graph with independent vertices, and a graph where two prerequisites point to one shared task. The returned sequence should contain every vertex exactly once, and for every edge source → target, the position of source should be smaller than the position of target.

Cycle tests should cover a two-vertex loop, a self-loop, and a cycle hidden behind an otherwise valid chain. For example, A → B, B → C, and C → B should fail even though A itself is straightforward. Also test disconnected components, because real dependency systems often contain several separate workflows.

Common mistakes include forgetting sink vertices, mutating the original indegree data when callers expect it to remain unchanged, and treating an arbitrary traversal order as the only correct answer. Another error is calculating indegrees only for dictionary keys while ignoring neighbours that appear exclusively in edge lists. Robust input handling should register every vertex before processing edges.

For a large graph, avoid repeatedly scanning every edge to find available vertices. Maintain indegrees incrementally and use an appropriate queue. If deterministic output matters for testing or deployment logs, sort initial zero-indegree vertices or use a heap, while remembering that deterministic ordering may add a logarithmic factor.

Practical recommendations for using topological sort

The following practices make a dependency sorter easier to maintain and safer to integrate:

• Store sparse directed graphs as adjacency lists rather than adjacency matrices.
• Keep a separate indegree count for Kahn’s algorithm and never infer readiness from vertex names.
• Check that the output contains every expected vertex before accepting the ordering.
• Treat a shorter result as a cycle or malformed input, not as a partial success.
• Use DFS for compact recursive code, but prefer an iterative method for very deep Python graphs.
• Add a deterministic queue or heap when reproducible build and deployment order matters.
• Test isolated vertices, duplicate edges, self-loops, disconnected components, and circular dependencies.

A topological sort is therefore more than a way to rearrange a list. It is a formal check that a set of directed prerequisites can be satisfied in sequence. Once the graph model is correct and cycle detection is included, the algorithm becomes a dependable foundation for scheduling, build automation, data processing, and dependency analysis.