Pattern visualizer
Topological Sort (BFS - Kahn's)
A topological order lists the vertices so that every arrow points forward. Kahn's idea: a vertex with no incoming arrows can safely go first, and once it is out, the arrows leaving it no longer matter — so the vertices it pointed at may become safe too. Keep one number per vertex, its remaining incoming count, and a queue of vertices whose count has hit 0. Popping from the front and pushing newly freed vertices at the back is what makes it breadth-first. The picture draws one directed arrow per edge and shows the remaining count as a badge. Animated on: numVertices = 6, edges = [[5,0],[5,2],[4,0],[4,1],[2,3],[3,1]] (a->b means a comes before b) — return a topological ordering using BFS..
Kahn's algorithm: output vertices as their incoming edges clear
A directed acyclic graph
6 vertices, 6 directed edges, and an arrow a to b means a must come before b in the answer. We are asked for an ORDER, so the plan is to output vertices one at a time and only ever output a vertex once everything pointing at it is already out.
1FUNCTION topoSort(n, edges):2 FOR v FROM 0 TO n - 13 indeg[v] <- 04 FOR EACH (a, b) IN edges5 APPEND b TO next[a]6 indeg[b] <- indeg[b] + 17 queue <- EVERY v WHERE indeg[v] = 08 order <- EMPTY LIST9 WHILE queue NOT EMPTY10 v <- REMOVE FIRST FROM queue11 APPEND v TO order12 FOR EACH w IN next[v]13 indeg[w] <- indeg[w] - 114 IF indeg[w] = 015 APPEND w TO queue16 RETURN order
← / → step · space play · Home restart