Pattern visualizer
Topological Sort (DFS)
Depth-first search gives a topological order almost for free, as long as you append a vertex when you LEAVE it, not when you enter it. Leaving means every vertex it points to has already been fully explored and appended, so the post-order list has each dependency after the thing that needs it — reverse the list and the order is correct. The picture below draws one arrow per edge, shows the live recursion stack in the side panel, and puts each vertex's position in the post-order list on its badge. Animated on: 7 vertices with edges 0->1, 0->2, 1->3, 2->3, 3->4, 5->2, 5->6 (u->v means u before v) — return a topological ordering using depth-first search..
Post-order DFS: a vertex finishes only after everything it points to
Vertices and directed edges
7 vertices, and an arrow u to v means u must come before v. DFS finds an order without ever counting prerequisites: a vertex is FINISHED only after everything it points to has finished, so finishing times run backwards through the dependencies.
1FUNCTION topoSortDFS(n, edges):2 FOR EACH (u, v) IN edges3 APPEND v TO next[u]4 order <- EMPTY LIST5 FOR u FROM 0 TO n - 16 IF NOT visited[u]7 dfs(u)8 RETURN REVERSE(order)9FUNCTION dfs(u):10 visited[u] <- true11 FOR EACH v IN next[u]12 IF NOT visited[v]13 dfs(v)14 APPEND u TO order
← / → step · space play · Home restart