1. One-Liner
A topological order of a DAG lists vertices so every edge u→v appears with u before v.
2. The Problem It Solves
Prerequisites: course schedules, build systems (Make), task scheduling with dependencies — any partial order you must linearize.
3. The Core Idea
DFS postorder (reverse finish times) or Kahn: repeatedly remove vertices with in-degree 0 (sources).
4. How It Works (Step-by-Step)
| Method | Steps |
|---|---|
| DFS | Run DFS; push vertex to order after exploring all outgoing edges; reverse |
| Kahn | Queue all in-degree 0; pop u, append, decrement neighbors' in-degree; repeat |
5. Dry Run Example
Edges: 0→1, 0→2, 1→3. Valid topsorts include 0,1,2,3 or 0,2,1,3. If you add 3→0, graph has a cycle — no topological order.
6. Key Properties
| Property | Value |
|---|---|
| Exists iff | Graph is a DAG |
| Not unique | Often many valid orders |
| Time | O(V + E) |
7. Where It Is Used
| System | Use |
|---|---|
| npm / Gradle | Task dependency order |
| Compiler | Symbol dependency resolution |
8. Interview Tips
Detect cycle during DFS (back edge) or when Kahn processes < V vertices. Follow-ups: longest path in DAG, critical path.
9. Comparison with Other Algorithms
| DFS topo | Kahn | |
|---|---|---|
| Style | Recursive stack | BFS-like queue |
| Cycle detect | Back edge | Count < V |
10. Complexity
| -- | -- |
|---|---|
| Time | O(V + E) |
| Space | O(V) |
Implementation Example (PYTHON)
def topological_sort_dfs(n, adj):
vis = [0] * n
order = []
def dfs(u):
vis[u] = 1
for v in adj[u]:
if vis[v] == 1: raise ValueError('cycle')
if vis[v] == 0: dfs(v)
vis[u] = 2
order.append(u)
for i in range(n):
if vis[i] == 0: dfs(i)
return order[::-1]