Topological sort

A topological sort of a directed acyclic graph (DAG) is an ordering of its nodes such that for every directed edge u → v, node u comes before node v in the ordering. In other words, all edges point "forward" in the sequence.

This is only possible when the graph has no cycles. If A depends on B and B depends on A, there is no valid order — hence "directed acyclic graph."

Where topological order appears

• Build systems. File B.o depends on A.h. Compile A.h before B.o.
• Course prerequisites. Take Introduction to Algorithms before Advanced Algorithms.
• Package managers. Install all dependencies before the package that needs them.
• Task scheduling. Any workflow where tasks have hard ordering constraints.

In each case, you want to process a node only after all nodes it depends on have been processed.

Kahn's algorithm

Kahn's algorithm is BFS-based and intuitive:

1. Compute the in-degree of every node (number of incoming edges).
2. Add all nodes with in-degree 0 to a queue — they have no dependencies.
3. While the queue is non-empty:
   • Dequeue node u and append it to the result.
   • For each neighbour v of u, decrement v's in-degree.
   • If v's in-degree reaches 0, enqueue it.
4. If the result contains all nodes, you have a valid topological order. If not, the remaining nodes are part of a cycle.

Graph: 0 → 1, 0 → 2, 1 → 3, 2 → 3

in-degrees: {0: 0, 1: 1, 2: 1, 3: 2}
Queue starts: [0]

Dequeue 0  → result [0], decrement 1 and 2 → both reach 0 → enqueue both
Dequeue 1  → result [0,1], decrement 3 → in-degree 1
Dequeue 2  → result [0,1,2], decrement 3 → in-degree 0 → enqueue
Dequeue 3  → result [0,1,2,3]  ✓ all 4 nodes present

Multiple valid orderings often exist. Kahn's gives one of them; the specific order within a level depends on the queue implementation.

DFS-based topological sort

An alternative uses DFS with post-order recording:

1. Run DFS on each unvisited node.
2. When DFS on node u is fully finished (all descendants visited), push u onto a stack.
3. Reverse the stack — nodes finish in reverse topological order.

def topo_dfs(graph):
    visited = set()
    stack = []
    def dfs(u):
        visited.add(u)
        for v in graph[u]:
            if v not in visited:
                dfs(v)
        stack.append(u)   # finished — push
    for node in graph:
        if node not in visited:
            dfs(node)
    return stack[::-1]    # reverse

The DFS-based approach is O(V + E) and competes with Kahn's on performance. Its main practical advantage: it naturally detects back edges (cycles) during the traversal.

Where to go next

Next: topo sort and cycle detection — a complete Python implementation of Kahn's with cycle detection, and a DFS-based 3-colour marking algorithm that identifies back edges in directed graphs.