Topics › Graphs › Topo Sort and Problems

Topological Sort DFS

Hard TUF ID 2821 SDE

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a directed acyclic graph with V vertices numbered 0 to V - 1; adj.get(u) lists every v with an edge u -> v. Return any topological order: a sequence containing every vertex once, in which u appears before v for every edge u -> v. Use depth-first search.

Constraints: 1 ≤ V ≤ 10^4, 0 ≤ E ≤ 10^5. Any valid order is accepted.

Example 1

V = 6, edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1
answer = [5, 4, 2, 3, 1, 0]    // what the DFS below produces; other orders are valid too

Every arrow points to the right: 5 before 2 and 0, 4 before 0 and 1, 2 before 3, 3 before 1.

Example 2

V = 4, edges: 2->0, 0->3, 3->1
answer = [2, 0, 3, 1]          // a chain has exactly one valid order

The BFS method (Kahn’s algorithm) builds the order from the front, repeatedly choosing a vertex nothing points to. The DFS method works from the back: it decides which vertices can safely go last. Approach 1 shows that idea in its slowest form, and Approach 2 shows how DFS gets it for free.

Approach 1: Brute force, repeatedly place a sink at the back

Intuition. Which vertex may go last? One that has no outgoing edge to anything still unplaced, because nothing is allowed to come after it in that case. Such a vertex is a “sink” of the remaining graph, and a DAG always has one: follow outgoing arrows from any vertex; without a cycle you cannot revisit, so you must eventually stop at a vertex with no way out. Place that sink in the last free slot, forget it, and repeat with the next slot from the back.

Algorithm.

1. For back = V - 1 down to 0:
2. Scan the vertices for one that is unplaced and whose out-neighbours are all placed.
3. If none exists, the graph has a cycle; return an empty array.
4. Put it at order[back] and mark it placed.

static int[] bruteForce(int V, List<List<Integer>> adj) {
    boolean[] placed = new boolean[V];
    int[] order = new int[V];
    for (int back = V - 1; back >= 0; back--) {
        int pick = -1;
        for (int u = 0; u < V && pick == -1; u++) {
            if (placed[u]) continue;
            boolean sink = true;                      // every edge out of u must point to a placed vertex
            for (int v : adj.get(u)) if (!placed[v]) { sink = false; break; }
            if (sink) pick = u;
        }
        if (pick == -1) return new int[0];            // no sink left: the graph has a cycle
        placed[pick] = true;
        order[back] = pick;
    }
    return order;
}

Complexity. Time O(V · (V + E)): each of the V rounds may rescan every vertex and every edge. Space O(V).

Every round re-checks edges that have not changed. The key question, “are all of u’s successors already placed?”, is answered naturally by DFS.

Approach 2: Optimal, DFS reverse post-order

Intuition. Run a DFS and watch the moment a call dfs(u) returns. By then, DFS has followed every edge out of u and fully finished every vertex reachable from u. That is exactly the condition from Approach 1: all of u’s successors are already done. So if we write each vertex into the array from the back at the moment it finishes, we get a valid order.

More precisely, take any edge u -> v. When dfs(u) looks at v, there are only two possibilities in a DAG:

• v is unvisited: DFS recurses into it, so v finishes before u does.
• v is visited: it cannot still be in progress (on the current path), because then v -> ... -> u -> v would be a cycle. So v has already finished.

Either way v finishes before u, so v is written further right, and u comes before v in the final order. Many implementations push each finished vertex onto a stack and pop them all at the end; writing from the back of an array is the same thing without the extra reversal.

Algorithm.

1. Keep visited[], the output array, and a pointer back starting at V.
2. For each unvisited vertex s, call dfs(s).
3. dfs(u): mark u; recurse into each unvisited v in adj.get(u); then write order[--back] = u.

static int[] optimal(int V, List<List<Integer>> adj) {
    boolean[] visited = new boolean[V];
    int[] order = new int[V];
    int[] back = {V};                                 // next free slot, filled from the end
    for (int s = 0; s < V; s++) {
        if (!visited[s]) dfs(adj, s, visited, order, back);
    }
    return order;
}

static void dfs(List<List<Integer>> adj, int u, boolean[] visited, int[] order, int[] back) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (!visited[v]) dfs(adj, v, visited, order, back);
    }
    order[--back[0]] = u;                             // everything reachable from u is already placed after it
}

The pointer is wrapped in a one-element array, int[] back, so the recursive calls can update it in place.

Dry run on example 1. Adjacency lists: 2: [3], 3: [1], 4: [0, 1], 5: [2, 0]; vertices 0 and 1 have no outgoing edges.

The roots were tried in the order 0, 1, 2, ..., yet the final sequence is correct. That is the strength of finishing times: they do not depend on starting from a source.

Complexity. Time O(V + E): every vertex is entered once and every edge examined once. Space O(V) for visited, the output and the recursion depth.

Approach 3: Optimal, iterative DFS with an explicit stack

Intuition. A long chain of tens of thousands of vertices can overflow Java’s call stack in Approach 2. Simulate the recursion instead. The stack holds the vertices currently “in progress”, and next[u] remembers which edge of u to try next, playing the role of the loop inside dfs(u). When the top vertex still has an edge to an unvisited vertex, push that vertex (the recursive call). When it has no edges left, pop it and write it from the back (the return). This visits vertices in exactly the same order as the recursion, so it produces the same output.

Algorithm.

1. For each unvisited s: mark it and push it.
2. While the stack is not empty, look at the top u.
   • If u has another edge u -> v, advance next[u]; if v is unvisited, mark it and push it.
   • Otherwise pop u and write order[--back] = u.
3. Return the order.

static int[] optimalIterative(int V, List<List<Integer>> adj) {
    boolean[] visited = new boolean[V];
    int[] next = new int[V];
    int[] order = new int[V];
    int back = V;
    Deque<Integer> stack = new ArrayDeque<>();
    for (int s = 0; s < V; s++) {
        if (visited[s]) continue;
        visited[s] = true;
        stack.push(s);
        while (!stack.isEmpty()) {
            int u = stack.peek();
            if (next[u] < adj.get(u).size()) {
                int v = adj.get(u).get(next[u]++);
                if (!visited[v]) {
                    visited[v] = true;
                    stack.push(v);
                }
            } else {
                stack.pop();
                order[--back] = u;                    // u finishes now
            }
        }
    }
    return order;
}

Complexity. Time O(V + E). Space O(V), all on the heap.

Edge cases and pitfalls

• Post-order, not pre-order. Writing a vertex when DFS enters it is wrong. With edges 0 -> 2 and 1 -> 2, entering order from root 0 is 0, 2, 1, which puts 2 before 1. Finishing order reversed gives 1, 0, 2, which is valid.
• Reverse the finishing order. Appending finished vertices to a list without reversing yields an order in which every edge points backwards. Filling from the back avoids the mistake.
• Start from every vertex. A DFS from vertex 0 alone may reach nothing. The tests include the chain 4 -> 3 -> 2 -> 1 -> 0, where every root before 4 finishes immediately.
• Cycles go unnoticed. On a graph with a cycle, plain reverse post-order still returns a permutation, just not a valid one. If the input is not guaranteed to be a DAG, track the “on current path” state as in cycle detection with DFS.
• Many valid answers. Test by checking that every edge points forward, not by comparing to one fixed list, unless the graph is a chain.
• Isolated vertices finish immediately and can land anywhere.

Related problems

• Topological Sort BFS builds the order from the front with in-degrees.
• Detect A cycle in a Directed Graph using DFS adds the “on path” check this method lacks.
• Kosaraju’s algorithm uses the same DFS finishing order as its first phase.
• Course Schedule II asks for a topological order of courses.
• Shortest path in DAG processes vertices in topological order.