DSA Tracker

Visualize

Topological Sort (DFS)

Post-order DFS: a vertex finishes only after everything it points to

time O(V + E)space O(V + E)

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.

Details

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.

Problem:Topological Sort (DFS)Medium

Post-order DFS: a vertex finishes only after everything it points to

step 1 / 15

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.

Pseudocode
1FUNCTION topoSortDFS(n, edges):
2  FOR EACH (u, v) IN edges
3    APPEND v TO next[u]
4  order <- EMPTY LIST
5  FOR u FROM 0 TO n - 1
6    IF NOT visited[u]
7      dfs(u)
8  RETURN REVERSE(order)
9FUNCTION dfs(u):
10  visited[u] <- true
11  FOR EACH v IN next[u]
12    IF NOT visited[v]
13      dfs(v)
14  APPEND u TO order

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. 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.
  2. Enter 0: the call stack is now 0. Its arrows go to 1 and 2. 0 cannot be appended yet, because anything it points to must land in the list before it.
  3. Enter 1: the call stack is now 0 > 1. Its arrows go to 3. 1 cannot be appended yet, because anything it points to must land in the list before it.
  4. Enter 3: the call stack is now 0 > 1 > 3. Its arrows go to 4. 3 cannot be appended yet, because anything it points to must land in the list before it.
  5. Enter 4: no arrow leaves it, so nothing has to go before it and it finishes at once — append 4 as item 1 of the post-order list 4. Pop it; the stack is 0 > 1 > 3.
  6. Every vertex 3 points to is finished, so 3 itself is finished: append it as item 2, giving 4, 3. Pop it; the stack is back to 0 > 1.
  7. Every vertex 1 points to is finished, so 1 itself is finished: append it as item 3, giving 4, 3, 1. Pop it; the stack is back to 0.
  8. Enter 2: the call stack is now 0 > 2. Its arrows go to 3 — 3 already finished, so only nothing is left to explore. 2 cannot be appended yet, because anything it points to must land in the list before it.
  9. Every vertex 2 points to is finished, so 2 itself is finished: append it as item 4, giving 4, 3, 1, 2. Pop it; the stack is back to 0.
  10. Every vertex 0 points to is finished, so 0 itself is finished: append it as item 5, giving 4, 3, 1, 2, 0. Pop it — the stack is empty, so this DFS is complete.
  11. The outer loop reaches 5, which is still unvisited: no arrow from 4, 3, 1, 2, 0 ever led here. Without this loop the vertices 5 of 7 finished so far would be the whole answer and 5 would be silently dropped. Start a fresh dfs(5).
  12. Enter 5: the call stack is now 5. Its arrows go to 2 and 6 — 2 already finished, so only 6 is left to explore. 5 cannot be appended yet, because anything it points to must land in the list before it.
  13. Enter 6: no arrow leaves it, so nothing has to go before it and it finishes at once — append 6 as item 6 of the post-order list 4, 3, 1, 2, 0, 6. Pop it; the stack is 5.
  14. Every vertex 5 points to is finished, so 5 itself is finished: append it as item 7, giving 4, 3, 1, 2, 0, 6, 5. Pop it — the stack is empty, so this DFS is complete.
  15. All 7 vertices finished; the post-order list is 4, 3, 1, 2, 0, 6, 5. Every vertex was appended AFTER everything it points to, so reading the list backwards puts each vertex BEFORE its dependents: RETURN 5, 6, 0, 2, 1, 3, 4. Every arrow now runs from a smaller badge to a larger one.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Topological Sort (DFS) in the editorAll Graph problemsBack to roadmap