Graph AlgosGraph Algorithms

DFS Topological Sort

Run DFS, record vertices as they finish, and reverse that list; a grey-to-grey edge during the search means a cycle.

Learn DFS Topological Sort →
shirttiejacketpantsbeltshoessocks
Recursion path
empty
Post-order (push as finished)
empty
1/19DFS post-order lists each node only after all of its descendants. Reversing that list therefore puts every node before the nodes it points to.
Current nodeOn recursion pathFinished (label = post-order position)DFS tree edge
PseudocodeLearn DFS Topological Sort →
1visited = {}; post = []
2def dfs(u):
3  visited.add(u)
4  for v in neighbors(u):
5    if v not in visited: dfs(v)
6  post.append(u)   # u finishes after all descendants
7for u in nodes: if u not in visited: dfs(u)
8return reversed(post)
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed