Topological Sort

Order vertices of a directed acyclic graph so every edge goes from earlier to later in the ordering.

O(V + E)Graphs
Phase 1f(x)

The Mathematics

DAG ordering, DFS finish times, and correctness

DAG & Topological Order

A Directed Acyclic Graph (DAG) is a directed graph G=(V,E)G = (V, E) with no cycles. A topological ordering is a linear ordering of vertices such that:

∀(u,v)∈E:u appears before v\forall (u, v) \in E: \quad u \text{ appears before } v

A topological order exists if and only if the graph is a DAG. A DAG with nn vertices may have many valid orderings.

DFS Finish-Time Ordering

DFS assigns each node a finish time — when all descendants have been explored. The key insight:

(u,v)∈E  ⇒  finish(u)>finish(v)(u, v) \in E \;\Rightarrow\; \text{finish}(u) > \text{finish}(v)

Sorting by decreasing finish time gives a valid topological order. Equivalently, push to a stack on finish and reverse:

topo_order=reverse([finish order])\text{topo\_order} = \text{reverse}([\text{finish order}])

Complexity

DFS visits every vertex and edge exactly once:

T(V,E)=O(V+E)T(V, E) = O(V + E)

Common Application

Course scheduling: if course A is a prerequisite of course B, then edge (A,B)(A, B) ensures A is scheduled before B. The topological sort gives a valid course sequence.

Phase 2▶

See It Work

DFS-based topological sort on a course-prerequisite DAG

ABCDEFG
Current In Progress Finished
visited=∅,stack=[]\text{visited} = \emptyset, \quad \text{stack} = []
Step 1 of 16

Initialize: no nodes visited. We will DFS from each unvisited node.

Phase 3</>

The Code

Bridge from DFS finish-time ordering to Python implementation

Mathematical Formulation

visited=∅\text{visited} = \emptyset

Track which nodes have been fully processed

stack=[]\text{stack} = []

Stack collects nodes in reverse topological order

u→visitedu \to \text{visited}

Mark node as visited when DFS enters it

(u,v)∈E  ∧  v∉visited(u, v) \in E \;\land\; v \notin \text{visited}

For each edge, recurse on unvisited neighbors

finish(u)⇒stack.push(u)\text{finish}(u) \Rightarrow \text{stack.push}(u)

Push node to stack when all descendants are processed (finish time)

reverse(stack)=topological order\text{reverse(stack)} = \text{topological order}

Reversing finish-time order gives valid topological ordering

Python Implementation

def topological_sort(graph):
    visited = set()
    stack = []

    def dfs(node):
        visited.add(node)              # Mark as visited
        for neighbor in graph[node]:   # Visit all neighbors
            if neighbor not in visited:
                dfs(neighbor)          # Recurse on unvisited
        stack.append(node)             # Push after all descendants done

    for node in graph:                 # Process all components
        if node not in visited:
            dfs(node)

    return stack[::-1]                 # Reverse = topological order