Topological Sort: Algorithms, Examples & Applications

Dependency order determines whether a build, data pipeline, or deployment can proceed correctly. Topological sort turns prerequisites into an ordering that respects every dependency, or establishes that a cycle makes a complete ordering impossible.

This guide explains the graph model, walks through Kahn's algorithm and depth-first search with Python examples, and covers their complexity, applications, and operational limits. It also shows how dependency data stored in tables can become the graph those algorithms consume.

What is topological sort?

A topological sort is a linear ordering of a directed graph's vertices in which every edge u → v places u before v. It exists exactly when the graph is a directed acyclic graph, or DAG. Vertices can represent tasks, packages, courses, or computed values; edges express the precedence constraints between them. This is the definition used in Princeton's directed-graphs reference.

Throughout this article, arrows point from a prerequisite to its dependent. If task B requires task A, the edge is A → B. Some systems store a relationship named depends_on in the opposite direction, so establish that convention before sorting.

Unlike sorting numbers, topological sorting does not compare values to produce ascending or descending order. Two tasks without a dependency path between them may appear in either relative order. The graph specifies a partial order; the output chooses one compatible sequence containing every vertex exactly once.

The same rule supports several practical applications:

Build and release workflows. A compiled artifact can precede tests and security scanning, with publishing dependent on both checks succeeding.

Data transformations. A daily aggregate can follow ingestion and normalization, while independent transformations remain free to run concurrently.

Course prerequisites. A prerequisite graph can order courses so that required foundations come first. Term availability and enrollment capacity still need separate planning.

These applications share a requirement: dependencies must describe actual prerequisites. An association between two objects does not automatically imply an execution order.

How does topological sorting work?

Consider a release with five tasks: fetch, build, test, scan, and publish. Fetching source precedes building the artifact. Testing and scanning both require that artifact. Publishing requires both checks.

The edges are fetch → build, build → test, build → scan, test → publish, and scan → publish. Two valid orders are:

fetch, build, test, scan, publish
fetch, build, scan, test, publish

The relative order of test and scan is flexible. Moving publish ahead of either would violate a dependency.

One way to construct an order is to repeatedly select a vertex with no remaining prerequisites. Initially only fetch qualifies. Removing it makes build eligible. Removing build makes both test and scan eligible. After both have been removed, publish qualifies.

Why can this process always advance in a nonempty DAG? If every remaining vertex had an incoming edge, following predecessors would eventually revisit a vertex in the finite graph, forming a cycle. An acyclic graph therefore always has somewhere to start.

For sorting, removing a vertex is bookkeeping. In a running workflow, its dependents become eligible only after the prerequisite has actually completed successfully under the workflow's rules.

Topological sort algorithm explained

Kahn's algorithm implements that repeated selection using an in-degree: the number of incoming edges at a vertex. It maintains a queue of vertices whose remaining in-degree is zero. The queue-based implementation accompanying Algorithms, 4th Edition demonstrates this approach.

The procedure has five steps:

1. Count the incoming edges for every vertex.
2. Queue every vertex whose count is zero.
3. Remove a queued vertex and append it to the output.
4. Decrement the count for each of its successors, queuing any that reach zero.
5. Continue until the queue is empty. Reject the graph if the output omits any vertex.

Here is a Python implementation. The adjacency dictionary maps prerequisites to lists of their immediate dependents. Node identifiers must be hashable, and successor collections must be reusable lists or tuples rather than one-shot iterators.

from collections import deque


def topological_sort_kahn(graph):
    indegree = {node: 0 for node in graph}
    for successors in graph.values():
        for successor in successors:
            indegree[successor] = indegree.get(successor, 0) + 1

    ready = deque(node for node, count in indegree.items() if count == 0)
    order = []

    while ready:
        node = ready.popleft()
        order.append(node)
        for successor in graph.get(node, ()):
            indegree[successor] -= 1
            if indegree[successor] == 0:
                ready.append(successor)

    if len(order) != len(indegree):
        raise ValueError("Graph contains a directed cycle")
    return order


graph = {
    "fetch": ["build"],
    "build": ["test", "scan"],
    "test": ["publish"],
    "scan": ["publish"],
    "publish": [],
}

print(topological_sort_kahn(graph))
# ['fetch', 'build', 'test', 'scan', 'publish']

Vertices mentioned only as successors are included automatically. An isolated vertex must appear as a dictionary key with an empty list, since no edge can reveal its existence. The function also returns an empty list for an empty graph.

With V vertices and E edges, counting and updating edges costs O(V + E) time, assuming constant-time dictionary operations. The queue, counters, and output use O(V) additional space; storing the adjacency lists takes O(V + E). Python's deque supports approximately O(1) appends and removals at either end, avoiding the shifting cost of removing the first element of a list.

Types of topological sorting algorithms

Kahn's algorithm and DFS-based sorting enforce the same ordering constraint through different bookkeeping. Their standard adjacency-list implementations both run in O(V + E) time.

Kahn's ready set is useful when work must be dispatched as prerequisites finish. DFS fits code that already traverses dependency paths and tracks completion. Neither inherently chooses the fastest execution schedule.

Two useful variations change how an order is selected or presented. A priority queue implemented with a binary heap can choose the smallest eligible identifier at each step, producing a repeatable lexicographic order. With constant-time key comparisons, this changes the time bound to O(E + V log V). NetworkX exposes this policy through lexicographical_topological_sort.

Alternatively, topological generations group vertices into successive dependency layers. Our example has four: {fetch}, {build}, {test, scan}, and {publish}. These layers show potential parallelism, but do not account for worker limits or task durations.

DFS-based topological sorting

Depth-first search follows a vertex's outgoing edges and records that vertex only after its successors have finished. That produces a postorder. Reversing it produces a topological order for a DAG, as explained in Jeff Erickson's treatment of DFS and topological sorting.

Cycle detection requires more information than a single visited flag. Use three states: unseen, active on the current DFS path, and finished. An edge to an active vertex closes a directed cycle. An edge to a finished vertex is safe: different branches can share a successor.

Using the same adjacency representation and graph from the previous example:

def topological_sort_dfs(graph):
    state = {}  # Missing = unseen, 1 = active, 2 = finished
    postorder = []

    def visit(node):
        if state.get(node) == 1:
            raise ValueError("Graph contains a directed cycle")
        if state.get(node) == 2:
            return

        state[node] = 1
        for successor in graph.get(node, ()):
            visit(successor)
        state[node] = 2
        postorder.append(node)

    for node in graph:
        if node not in state:
            visit(node)

    return postorder[::-1]


print(topological_sort_dfs(graph))
# ['fetch', 'build', 'scan', 'test', 'publish']

Here DFS reaches publish through test and finishes it first. It then finishes test, explores scan, and eventually finishes build and fetch. Reversing that finishing order places every prerequisite before its dependents. The result differs from Kahn's output but satisfies exactly the same constraints.

The outer loop matters for disconnected graphs: starting DFS from just one vertex can leave whole components unvisited. The implementation uses O(V + E) time and O(V) additional space, including the call stack. Long chains can reach Python's recursion limit; use Kahn's algorithm or an explicit DFS stack when depth is unbounded.

Advantages and limitations of topological sort

Efficient dependency ordering. Linear time makes a single sort practical for graphs that fit the chosen representation and memory budget. It processes direct dependencies without requiring an explicit edge for every transitive relationship. If fetch → build and build → test exist, an additional fetch → test edge is unnecessary for ordering.

Explicit validation. A successful sort establishes that the represented precedence constraints are acyclic. Failure identifies a dependency problem before execution, although diagnosing the exact cycle may require additional traversal. The guarantee concerns the supplied graph; a missing dependency remains missing after sorting.

Limited scheduling information. An order says which tasks must precede others, not when they should start. It contains no resource capacities, deadlines, execution costs, or retry policies. Two tasks may be independent in the graph yet compete for the same exclusive deployment lock.

No solution for cyclic prerequisites. If A requires B and B requires A, neither can satisfy the strict precedence rule. Package version selection introduces another limitation: sorting a chosen package graph does not decide which versions satisfy all compatibility constraints.

Treat the result as a dependency-respecting input to a scheduler or planner. That component still decides when eligible work runs and what to do when it fails.

Topological sorting challenges

Distinguishing cycles from their consequences. Suppose test → scan, scan → test, and both lead to publish. Kahn's algorithm leaves all three unprocessed. Only test and scan belong to the cycle; publish is blocked downstream. Reporting every leftover vertex as a cycle member misdirects debugging.

Strongly connected components can isolate groups with mutual reachability. Components containing multiple vertices, or a single vertex with a self-loop, identify cyclic regions. Contracting each component produces an acyclic condensation graph. That can order groups for analysis, but it does not resolve execution order inside a cyclic group.

Changing dependencies. Adding an edge after sorting can invalidate the order or create a cycle. For example, adding scan → test invalidates our first sample order while preserving the second. Record which graph version an order describes and recompute when its dependencies change.

Incomplete or inconsistent inputs. Dependency records may omit isolated tasks, mix identifier namespaces, or reverse edge direction. Counting duplicate edges during initialization but deduplicating them during traversal also leaves incorrect in-degree values. Normalize the representation before sorting.

Moving data into memory. The O(V + E) bound describes sorting an already constructed graph. Reading remote tables, transferring records, and constructing the input graph add preparation time. Scope the workload deliberately, including all unresolved prerequisites required by the selected tasks.

Topological sort best practices

Validate the invariant. Check that the output is a permutation of the expected vertices, with no duplicates, omissions, or extra vertices. Then build a position map and verify position[u] < position[v] for every edge. This tests correctness even when several answers are valid. Cover disconnected components, isolated vertices, self-loops, and cycles alongside ordinary DAGs.

Make ordering policy explicit. Stable input iteration can make a queue-based implementation repeatable. If consumers require a canonical sequence regardless of input order, define a unique, comparable key and use a priority queue. Avoid treating a different valid sequence as a regression.

Use library support where it fits. Python's graphlib.TopologicalSorter accepts a mapping from each node to its predecessors, the reverse of our adjacency representation:

from graphlib import TopologicalSorter

predecessors = {node: [] for node in graph}
for prerequisite, dependents in graph.items():
    for dependent in dependents:
        predecessors.setdefault(dependent, []).append(prerequisite)

print(list(TopologicalSorter(predecessors).static_order()))
# ['fetch', 'build', 'test', 'scan', 'publish']

For execution, its get_ready() and done() methods support tracking readiness as work completes. Your executor must handle failures and report completion according to its dependency policy. A static list alone cannot track those transitions.

Model dependency data where it is maintained. A release catalog might store artifacts in one table and prerequisite relationships in another. PuppyGraph lets you define a graph schema over those existing tables and query them with openCypher and Gremlin. Its table-to-graph mapping assigns identifiers, node types, edge endpoints, and properties. In this example, an Artifact node and a prerequisite-to-dependent PRECEDES edge give queries a consistent dependency vocabulary.

Through the default direct-query path, the data stays in supported SQL databases, warehouses, or lakehouses, with no graph-specific ETL into a separate graph database. You can query dependency paths to investigate which downstream artifacts a change affects, then retrieve the vertices and edges needed for a bounded planning task. Include unresolved prerequisites outside the initially affected set before scheduling it. Here, Python performs the topological sort, and the workflow executor controls task execution. PuppyGraph supplies the queryable relationship model over the source data.

Conclusion

Topological sort translates acyclic precedence constraints into a valid sequence. Kahn's algorithm tracks remaining prerequisites; DFS reverses finishing order. Both are linear-time approaches whose usefulness depends on accurate edge direction, complete inputs, and explicit handling of cycles. Execution still needs a scheduler that accounts for completion, resources, and failures.

Try the forever-free PuppyGraph Developer Edition and book a demo with the team to see how openCypher and Gremlin queries trace dependencies across warehouse and lakehouse tables, with no graph-specific ETL, to prepare dependency data for ordering and impact analysis.