Topological Sort

DFS Post-Order

Run DFS on every unvisited node. After processing ALL of a node's descendants, push it to a stack. The stack (reversed) gives the topological order. A node is pushed only after everything it depends on is already processed.

O(V + E)

O(V)

How It Works

The DFS approach to topological sorting relies on finish times. Run DFS from every unvisited node; when a node's entire subtree of descendants has been fully explored, push the node onto a stack. Because a node is pushed only after everything reachable from it, popping the stack (reversing the push order) yields an order where every node precedes all nodes it points to — a valid topological order for a DAG.

The cost is a single traversal, O(V + E) time and O(V) space for the visited set and stack. The correctness argument is that for any edge u→v, DFS must finish v before it finishes u — either v was explored during u's call or was already complete — so v sits deeper in the stack and appears after u in the final order.

Step-by-Step Visualization

DFS-based topological sort

Start DFSfrom node 5

1/4

Code

Java

static int[] topoSortDFS(Map<Integer, List<Integer>> graph, int n) {
  Set<Integer> visited = new HashSet<>();
  Stack<Integer> stack = new Stack<>();

  for (int i = 0; i < n; i++)
    if (!visited.contains(i)) dfs(graph, i, visited, stack);

  int[] result = new int[n];
  for (int i = 0; i < n; i++) result[i] = stack.pop();
  return result;
}

static void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited, Stack<Integer> stack) {
  visited.add(node);
  for (int nei : graph.getOrDefault(node, Collections.emptyList())) {
    if (!visited.contains(nei)) dfs(graph, nei, visited, stack);
  }
  stack.push(node); // Post-order
}

Tips & Gotchas

1Process node AFTER all its descendants are processed (post-order)

2Push to result stack after DFS completes for a node

3Reverse the result for topological order

Practice Problems

1Course Schedule II
2Longest Increasing Path in a Matrix
3Sort Items by Groups Respecting Dependencies
4All Ancestors of a Node in a Directed Acyclic Graph

About the Topological Sort Pattern

Order the nodes of a directed graph so that for every edge A→B, A comes before B. Only works on DAGs (directed acyclic graphs). If a cycle exists, topological sort is impossible — which is how you detect cycles.

Key insight

Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.

Common Graphs Interview Problems

Number of Islands
Clone Graph
Course Schedule
Pacific Atlantic Water Flow
Network Delay Time
Minimum Spanning Tree
Word Ladder

Frequently Asked Questions

Why is the stack reversed at the end?

Nodes are pushed in order of completion, so sinks — nodes with no outgoing edges — get pushed first and end up at the bottom. Reversing puts sources first and dependents later, which is the direction a topological order requires.

Does DFS post-order alone detect cycles?

Not by itself — a plain visited flag cannot distinguish a back edge from a cross edge. You must add an 'in progress' state (the gray color): revisiting a gray node means a cycle, and only then is the produced ordering trustworthy.