Graph AlgosGraph Algorithms

Kahn's Algorithm (BFS topological sort)

Topologically sort a DAG by repeatedly emitting vertices whose in-degree has dropped to zero; leftover vertices reveal a cycle.

Learn Kahn's Algorithm →
shirt0tie1jacket2pants0belt2shoes2socks0
Queue
shirtpantssocks
Topological order
empty
1/16Count incoming edges. Nodes with in-degree 0 have no prerequisites, so they can go first: shirt, pants, socks.
Current node (label = in-degree)In queue (in-degree 0)EmittedEdge being removedStuck in a cycle
PseudocodeLearn Kahn's Algorithm →
1indeg[v] = number of incoming edges
2queue = [v for v in nodes if indeg[v] == 0]
3while queue not empty:
4  u = queue.popleft(); order.append(u)
5  for v in neighbors(u):
6    indeg[v] -= 1
7    if indeg[v] == 0: queue.append(v)
8if len(order) < n: cycle detected
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed