DFS-Based Topological Sort

The Ordering Problem

A directed edge often means “must happen before.” If a compiler records parse → type-check, then parsing must precede type checking. If a course catalog records Calculus I → Calculus II, the first course must appear earlier in any valid plan. A topological order is a linear arrangement of all vertices that respects every such constraint.

The requirement is possible if and only if the graph is a directed acyclic graph (DAG). A cycle such as $A\to B\to C\to A$ asks each item to come before itself after following the constraints around the loop—an impossible schedule. A DAG can have one valid order or many; vertices with no ordering constraint between them may trade places.

The Finish-Time Intuition

DFS has two important moments for each vertex. Its discovery time is when DFS first enters it; its finish time is when every outgoing edge has been examined and the call returns. Topological sorting uses the second moment. Appending on discovery is tempting, but it can place a vertex too early when a later DFS tree contains one of its prerequisites. Appending on finish captures the complete dependency story.

Reverse Postorder Algorithm

The finish sequence is also called postorder, because a vertex is recorded after its outgoing neighbors are processed. Reading it backward gives reverse postorder.

1. Initialize every vertex to white and create an empty list order.
2. Start DFS from every still-white vertex. This outer loop matters because the graph may be disconnected.
3. On entry, color the vertex gray. Recursively visit each white outgoing neighbor.
4. If an outgoing neighbor is gray, report a cycle; no topological order exists.
5. After all neighbors are processed, color the vertex black and append it to order.
6. Reverse order after all DFS trees finish.

You do not need literal timestamps. The append position acts as the finish-time rank. A stack is equivalent: push on finish and later pop everything. In an array-backed implementation, append and one final reversal are usually simpler.

Worked DFS Trace

Use the dependency DAG $A\to C$, $B\to C$, $B\to D$, and $C\to D$. Assume the outer loop examines vertices in the order $A,B,C,D$, and each adjacency list is read as shown.

The result is not unique: A, B, C, D is also valid. DFS returns one valid answer determined by the vertex iteration order and adjacency-list order. Unless the application asks for a specific tie-breaking rule, either answer is correct.

Why Reversing Finish Times Is Correct

Claim. In a DAG, every edge $(u,v)$ satisfies $f(u)>f(v)$, where $f(x)$ is the DFS finish time of $x$. Therefore decreasing finish time puts $u$ before $v$.

Consider the state of $v$ when DFS examines edge $(u,v)$:

• $v$ is white. DFS enters $v$ and finishes its entire reachable subtree before it can return to $u$. Hence $f(v)<f(u)$.
• $v$ is black. It already finished, while $u$ is still active. Again $f(v)<f(u)$.
• $v$ is gray. Then $v$ is an ancestor of $u$ on the active recursion stack, and $(u,v)$ closes a directed cycle. This case cannot occur in a DAG.

The first two cases cover every edge of a DAG, so reversing finish order respects all edges. Notice what the proof does not require: it does not require the graph to be connected, the start vertex to be a source, or the topological order to be unique.

Cycle Detection Comes for Free

The same three colors that explain correctness also reject invalid input. While processing $u$, an edge to a gray vertex $v$ is a back edge. The recursion stack already contains a path $v\leadsto u$; adding $u\to v$ completes a cycle.

If you need the actual cycle rather than a Boolean flag, retain each vertex's parent. When $u\to v$ reaches gray $v$, walk parent pointers from $u$ back to $v$, then append the closing edge. This turns the failure report into a useful explanation such as A → B → C → A.

Implementation

The three-color form is preferable to a single visited array because it distinguishes “currently active” from “already complete.” That distinction is exactly what detects a back edge. The implementations below also run DFS from every white vertex, so isolated vertices and disconnected DAG components are included.

def dfs_topological_sort(n, adj):
    """
    n: number of vertices
    adj: adj[u] = list of neighbors v (directed edges u -> v)
    Returns a topological order, or None if a cycle is detected.
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    order = []
    has_cycle = [False]

    def dfs(u):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == WHITE:
                dfs(v)
            elif color[v] == GRAY:
                has_cycle[0] = True  # back edge -> cycle detected
        color[u] = BLACK
        order.append(u)  # record finish order

    for u in range(n):
        if color[u] == WHITE:
            dfs(u)

    if has_cycle[0]:
        return None

    order.reverse()  # reverse postorder = topological order
    return order

# Example: A=0, B=1, C=2, D=3;  A->C, B->C, C->D, B->D
n = 4
adj = [[] for _ in range(n)]
edges = [(0, 2), (1, 2), (2, 3), (1, 3)]
for u, v in edges:
    adj[u].append(v)

print("Topological order:", dfs_topological_sort(n, adj))

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(int u, vector<vector<int>>& adj, vector<int>& color,
         vector<int>& order, bool& hasCycle) {
    color[u] = 1; // GRAY

    for (int v : adj[u]) {
        if (color[v] == 0) {
            dfs(v, adj, color, order, hasCycle);
        } else if (color[v] == 1) {
            hasCycle = true; // back edge
        }
    }

    color[u] = 2; // BLACK
    order.push_back(u);
}

vector<int> dfsTopologicalSort(int n, vector<vector<int>>& adj) {
    vector<int> color(n, 0); // 0=WHITE, 1=GRAY, 2=BLACK
    vector<int> order;
    bool hasCycle = false;

    for (int u = 0; u < n; u++) {
        if (color[u] == 0) {
            dfs(u, adj, color, order, hasCycle);
        }
    }

    if (hasCycle) return {};

    reverse(order.begin(), order.end());
    return order;
}

int main() {
    int n = 4;
    vector<vector<int>> adj(n);
    vector<pair<int, int>> edges = {{0, 2}, {1, 2}, {2, 3}, {1, 3}};
    for (auto& e : edges) adj[e.first].push_back(e.second);

    vector<int> order = dfsTopologicalSort(n, adj);
    cout << "Topological order: ";
    for (int v : order) cout << v << " ";
    cout << endl;
    return 0;
}

import java.util.*;

public class DFSTopologicalSort {
    static boolean hasCycle = false;

    static void dfs(int u, List<List<Integer>> adj, int[] color, List<Integer> order) {
        color[u] = 1; // GRAY

        for (int v : adj.get(u)) {
            if (color[v] == 0) {
                dfs(v, adj, color, order);
            } else if (color[v] == 1) {
                hasCycle = true; // back edge
            }
        }

        color[u] = 2; // BLACK
        order.add(u);
    }

    public static List<Integer> solve(int n, List<List<Integer>> adj) {
        int[] color = new int[n]; // 0=WHITE, 1=GRAY, 2=BLACK
        List<Integer> order = new ArrayList<>();
        hasCycle = false;

        for (int u = 0; u < n; u++) {
            if (color[u] == 0) {
                dfs(u, adj, color, order);
            }
        }

        if (hasCycle) return null;

        Collections.reverse(order);
        return order;
    }

    public static void main(String[] args) {
        int n = 4;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        int[][] edges = {{0, 2}, {1, 2}, {2, 3}, {1, 3}};
        for (int[] e : edges) adj.get(e[0]).add(e[1]);

        List<Integer> order = solve(n, adj);
        System.out.println("Topological order: " + order);
    }
}

API note: the compact C++ sample uses an empty vector to signal a cycle. If an empty graph is valid input in your application, return a structured result such as std::optional<vector<int>> or pair the vector with an explicit success flag so “valid but empty” and “cycle” remain distinct.

Iterative DFS Without Call-Stack Risk

A recursive implementation mirrors the proof, but a chain of $V$ vertices creates recursion depth $V$. In Python, Java, and many production environments, a sufficiently long chain can overflow the call stack. An explicit stack avoids that limit—but each stack frame must remember which neighbor comes next. A stack of vertices alone cannot reproduce the “append after all children” moment reliably.

def iterative_topological_sort(n, adj):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    postorder = []

    for start in range(n):
        if color[start] != WHITE:
            continue

        color[start] = GRAY
        # frame = [vertex, index of next neighbor to examine]
        stack = [[start, 0]]

        while stack:
            u, next_index = stack[-1]

            if next_index < len(adj[u]):
                v = adj[u][next_index]
                stack[-1][1] += 1

                if color[v] == WHITE:
                    color[v] = GRAY
                    stack.append([v, 0])
                elif color[v] == GRAY:
                    return None  # back edge: no topological order
            else:
                stack.pop()
                color[u] = BLACK
                postorder.append(u)

    postorder.reverse()
    return postorder

Complexity & Choosing Between DFS and Kahn

Each vertex changes color a constant number of times, and each directed edge is examined once from its source's adjacency list.

The space includes colors, the result, and either the recursive or explicit DFS stack. The adjacency list itself occupies $O(|V|+|E|)$ input storage. With an adjacency matrix, scanning every possible neighbor changes traversal time to $O(|V|^2)$ even when the graph is sparse.

Choose DFS when the surrounding algorithm already uses DFS state, when an explicit cycle witness is useful, or when reverse postorder feeds a later DAG dynamic program. Choose Kahn's algorithm when you need to expose all currently available tasks, process in waves, or enforce a smallest-first tie-break with a priority queue.

Validate the Result—and Recognize Uniqueness

A small checker catches reversed edge semantics and implementation mistakes. Build position[v], then verify position[u] < position[v] for every edge $u\to v$. This costs another $O(V+E)$ pass and is invaluable in tests.

def is_topological_order(n, edges, order):
    if order is None or len(order) != n or len(set(order)) != n:
        return False
    if any(v < 0 or v >= n for v in order):
        return False

    position = [0] * n
    for i, v in enumerate(order):
        position[v] = i

    return all(position[u] < position[v] for u, v in edges)

A DAG has a unique topological order exactly when every consecutive pair $v_i,v_{i+1}$ in a topological order has the edge $v_i\to v_{i+1}$. If no edge connects a consecutive pair, swapping those two preserves all constraints, producing another valid order. In Kahn's view, uniqueness means there is exactly one zero-in-degree choice at every step.

Real-World Applications

Topological order is less an end product than a permission slip: once dependencies point forward, many hard-looking graph tasks become a single left-to-right pass.

Pitfalls & Implementation Checklist

Exercises

1. Trace the algorithm on the diamond DAG $A\to B$, $A\to C$, $B\to D$, $C\to D$. Change the adjacency order of $A$ and explain why the returned topological order changes.
2. Add parent pointers and return one concrete directed cycle instead of only None.
3. Implement the iterative algorithm without storing a neighbor index by using explicit enter and exit events. Compare the two stack designs.
4. Use the validator to generate random DAGs, shuffle adjacency lists, and confirm that every returned order respects every edge.
5. Prove the consecutive-edge criterion for a unique topological order.
6. Challenge: enumerate all valid topological orders with backtracking. Why can the output itself be exponential?

Historical Note

Topological ordering has several classic linear-time formulations. Arthur Kahn described the in-degree-removal approach in 1962. Robert Tarjan's influential 1972 work developed depth-first search as a systematic foundation for linear-time graph algorithms. Today, “DFS topological sort” usually refers to the reverse-postorder technique explained here, while “Kahn's algorithm” refers to repeatedly removing a zero-in-degree vertex.