Course contentsShow
← Computer Science
Lesson 725 of 2,87217. Graph Traversal AlgorithmsFree lesson

DFS Topological Sort: Correctness

Prove why reverse post-order of DFS produces a valid topological ordering.

DFS Topological Sort: Correctness

You'll learn why reversing the finish order from DFS always produces a valid topological ordering.

The Core Idea

When we run DFS on a directed acyclic graph (DAG) and reverse the order in which vertices finish (complete all their explorations), we get a valid topological sort. But why does this work?

The key insight: a vertex finishes only after all its descendants finish. In DFS, we explore as deep as possible before backtracking. When we finish exploring vertex u, we've already finished all vertices reachable from u.

Why Reverse Post-Order Works

Consider any edge u → v in the DAG:

Case 1: We visit u before v
DFS explores from u, discovers v, and finishes v before finishing u. So v finishes first, u finishes second. In reverse post-order, u comes before v. ✓

Case 2: We visit v before u
Since there's an edge u → v but we haven't seen u yet when visiting v, u cannot be reachable from v (otherwise we'd have a cycle, violating the DAG property). Thus v finishes completely before we ever start u. Again, in reverse post-order, u comes before v. ✓

Think of it like getting dressed: you must put on socks before shoes. DFS finishes exploring "socks" first (including all things socks depend on). When reversed, socks appear before shoes in the final order.

Key Takeaway: DFS topological sort is correct because reversing finish times ensures every vertex appears before all vertices it points to—any edge u → v guarantees u finishes after v, placing u before v in the reversed sequence.