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

DFS-Based Topological Sort

Use depth-first search with post-order traversal to generate topological ordering.

DFS-Based Topological Sort

What You'll Learn

You'll learn how to generate a topological ordering by running depth-first search and recording vertices in reverse order of their completion.

The Core Idea

Remember that topological sorting arranges vertices in a directed acyclic graph (DAG) so that all edges point "forward" in the ordering. The DFS-based approach uses a clever insight: if you record vertices in reverse order of when DFS finishes exploring them, you get a valid topological sort.

Here's why this works: when DFS finishes with a vertex (meaning all its descendants have been explored), that vertex has no outgoing edges to unexplored nodes. By recording it at this moment, we guarantee that any vertex depending on it will appear earlier in our reversed list.

The Algorithm

  1. Run DFS on all unvisited vertices in the graph
  2. Track finish times: when DFS completely finishes exploring a vertex (after visiting all its neighbors), add it to a list
  3. Reverse the list at the end—this gives you the topological order

Think of it like getting dressed: you can't finish putting on your shoes until you've finished putting on your socks. DFS naturally explores dependencies first, so the last thing you "finish" has no dependencies left—it can go first in the final ordering.

How It Differs from Kahn's Algorithm

While Kahn's algorithm removes vertices with no incoming edges (building the order front-to-back), DFS builds from the "end" backward—finding vertices that nothing else depends on, then working toward the start.

Key Takeaway: DFS-based topological sort records vertices in post-order (when DFS finishes with them), then reverses that list to produce a valid topological ordering—leveraging the natural dependency resolution of depth-first traversal.