Topological Sort: Kahn and DFS
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Real work has rules like "pay before shipping". A topological sort turns such rules into one valid order. This lesson builds it two ways, both in O(V + E) time, and shows how the same code finds a cycle.
Putting tasks in a valid order
A topological order is a list of all nodes of a directed graph in which every edge u → v has u before v. It exists exactly when the graph has no cycle.
Each rule "A before B" is a directed edge A → B. A valid plan lists every task so that each edge points forward. Such a list exists only when the rules never loop back.
Example 1 · Brute force: try every order
from itertools import permutations
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
def valid(order): pos = {node: i for i, node in enumerate(order)} return all(pos[u] < pos[v] for u, v in edges)
for order in permutations(range(4)): if valid(order): print(order) break(0, 1, 2, 3)
What this code does
- It tries all n! orders and checks each edge, so the time is O(n! * E). Four nodes are fine; twenty are impossible.
enumeratebuilds a position table so each check is one comparison.
Kahn's algorithm: remove nodes with nothing left to wait for
The in-degree of a node is the number of edges coming in. A node with in-degree 0 has no unfinished prerequisite, so it can go first. Take it out, lower its neighbours' in-degrees, and repeat.
queue = deque(i for i in range(n) if indeg[i] == 0)order = []while queue: u = queue.popleft() order.append(u) for v in graph[u]: indeg[v] -= 1 if indeg[v] == 0: queue.append(v)Example 2 · Build the graph and the in-degrees
def build(n, edges): graph = [[] for _ in range(n)] indeg = [0] * n for u, v in edges: graph[u].append(v) indeg[v] += 1 return graph, indeg
graph, indeg = build(5, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)])print(graph)print(indeg)[[1, 2], [3], [3], [4], []] [0, 1, 1, 2, 1]
What this code does
graph[u]lists the nodes that come after u.indeg[v]counts the edges that point into v.- Nodes with in-degree 0, here only node 0, can start.
Example 3 · Kahn's algorithm
from collections import deque
def build(n, edges): graph = [[] for _ in range(n)] indeg = [0] * n for u, v in edges: graph[u].append(v) indeg[v] += 1 return graph, indeg
def kahn(n, edges): graph, indeg = build(n, edges) queue = deque(i for i in range(n) if indeg[i] == 0) order = [] while queue: u = queue.popleft() order.append(u) for v in graph[u]: indeg[v] -= 1 if indeg[v] == 0: queue.append(v) return order if len(order) == n else None
print(kahn(5, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]))print(kahn(4, [(3, 0), (3, 1), (0, 2), (1, 2)]))[0, 1, 2, 3, 4] [3, 0, 1, 2]
What this code does
- The queue holds nodes that are ready. Node 3 starts in the second graph because nothing points to it.
- Time O(V + E), space O(V + E) for the lists.
Each node enters the queue once and each edge is looked at once, so the time is O(V + E). A deque pops from the front in O(1); list.pop(0) would be O(n).
DFS: a node ends after everything it leads to
Depth-first search visits a node, then all nodes reachable from it. A node is added to a list only when it is finished, so its successors are already there. Reverse the list for the order.
def dfs_order(n, graph): seen = [False] * n post = []
def visit(u): seen[u] = True for v in graph[u]: if not seen[v]: visit(v) post.append(u)
for u in range(n): if not seen[u]: visit(u) return post[::-1]Example 4 · DFS with a reversed post-order
def dfs_order(n, graph): seen = [False] * n post = []
def visit(u): seen[u] = True for v in graph[u]: if not seen[v]: visit(v) post.append(u)
for u in range(n): if not seen[u]: visit(u) return post[::-1]
graph = [[1, 2], [3], [3], [4], []]print(dfs_order(5, graph))[0, 2, 1, 3, 4]
What this code does
- Node 4 finishes first, then 3, 1 and 2, and node 0 last. Reversing gives an order where every edge points forward.
- DFS may return a different valid order than Kahn. Both are correct.
This is O(V + E) time and O(V) space. Python limits recursion to about 1000 calls, so for long chains use Kahn or raise the limit with sys.setrecursionlimit.
Finding a cycle
If the graph has a cycle, no node in it ever reaches in-degree 0, so Kahn's algorithm stops early. Compare the length of the order with the number of nodes. A shorter list means a cycle exists.
Example 5 · Detect a cycle
from collections import deque
def build(n, edges): graph = [[] for _ in range(n)] indeg = [0] * n for u, v in edges: graph[u].append(v) indeg[v] += 1 return graph, indeg
def kahn(n, edges): graph, indeg = build(n, edges) queue = deque(i for i in range(n) if indeg[i] == 0) order = [] while queue: u = queue.popleft() order.append(u) for v in graph[u]: indeg[v] -= 1 if indeg[v] == 0: queue.append(v) return order if len(order) == n else None
print(kahn(3, [(0, 1), (1, 2), (2, 0)]))print(kahn(4, [(0, 1), (1, 2)]))None [0, 3, 1, 2]
What this code does
- The first graph is a ring, so no node has in-degree 0 and the result is
None. - The second graph has no cycle. Node 3 has no edges, so it is ready from the start.
Example 6 · Smallest order first with heapq
import heapq
edges = [(2, 1), (2, 3), (1, 4), (3, 4), (0, 3)]n = 5graph = [[] for _ in range(n)]indeg = [0] * nfor u, v in edges: graph[u].append(v) indeg[v] += 1heap = [i for i in range(n) if indeg[i] == 0]heapq.heapify(heap)order = []while heap: u = heapq.heappop(heap) order.append(u) for v in graph[u]: indeg[v] -= 1 if indeg[v] == 0: heapq.heappush(heap, v)print(order)[0, 2, 1, 3, 4]
What this code does
- A min-heap always hands out the smallest ready node, so the order is the smallest possible one when compared from the front.
- The cost grows to O((V + E) log V) because each push and pop costs O(log V).
Next step
Check your understanding
11 quick questions