DFS-based Topological Sort: post-order reverse

• DFS from each unvisited node – explore all reachable descendants before recording a node.
• Post-order recording – push a node onto a stack only after all its descendants are fully explored.
• Reverse to get order – the reversed stack is a valid topological order.
• Three-color cycle detection – white (unvisited), gray (in progress), black (finished); a gray-to-gray edge is a cycle.
• O(V + E) time – each node and edge is visited once.

What is the problem?

Produce a topological order of a DAG using depth-first search. In a banking context, a report-generation pipeline at National Bank of India has stages that depend on upstream stages, and Pankaj needs them in dependency order.

How does DFS topological sort work?

For each unvisited node, run DFS that first recurses into all successors, then records the node after those recursions return (post-order). Push each finished node onto a stack. After all nodes are processed, pop the stack to get the topological order.

package com.bank.service;

import java.util.*;

public class ReportPipelineScheduler {

    private static final int WHITE = 0, GRAY = 1, BLACK = 2;

    public static List<Integer> topologicalSort(int numStages, int[][] deps) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numStages; i++) adj.add(new ArrayList<>());
        for (int[] d : deps) adj.get(d[0]).add(d[1]);

        int[] color = new int[numStages];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < numStages; i++) {
            if (color[i] == WHITE) {
                dfs(i, adj, color, stack);
            }
        }

        List<Integer> order = new ArrayList<>();
        while (!stack.isEmpty()) order.add(stack.pop());
        return order;
    }

    private static void dfs(int u, List<List<Integer>> adj,
                            int[] color, Deque<Integer> stack) {
        color[u] = GRAY;
        for (int v : adj.get(u)) {
            if (color[v] == GRAY) {
                throw new IllegalStateException("Cycle detected at node " + v);
            }
            if (color[v] == WHITE) {
                dfs(v, adj, color, stack);
            }
        }
        color[u] = BLACK;
        stack.push(u);
    }

    public static void main(String[] args) {
        // 0=Load data, 1=Validate, 2=Transform, 3=Aggregate, 4=Render
        int[][] deps = {{0,1}, {0,2}, {1,3}, {2,3}, {3,4}};
        List<Integer> schedule = topologicalSort(5, deps);
        String[] names = {"Load data", "Validate", "Transform",
            "Aggregate", "Render"};
        System.out.println("Report pipeline order:");
        for (int s : schedule) {
            System.out.println("  " + s + ": " + names[s]);
        }
    }
}

Report pipeline order:
  0: Load data
  2: Transform
  1: Validate
  3: Aggregate
  4: Render

Why reverse the post-order?

DFS finishes descendants before ancestors, so the raw post-order places each node after its successors. Reversing this puts each node before its successors, which is the topological order.

How do the three colors detect cycles?

White means unvisited, gray means currently on the recursion path, and black means fully explored. If DFS reaches a gray node, that is a back edge forming a cycle. A black node reached from a different path is not a cycle: it was just already explored.

if (color[v] == GRAY) {
    // Back edge: v is on current path → cycle
    throw new IllegalStateException("Cycle detected");
}
if (color[v] == BLACK) {
    // Cross/forward edge: v already finished → safe, skip
}

What is the time and space complexity?

• Time: O(V + E) because each node and edge is visited once.
• Space: O(V) for the color array, recursion stack, and output stack.

How is this different from Kahn's algorithm?

| Aspect | DFS-based | Kahn's (BFS) |
|---|---|---|
| Approach | Post-order reversal | Zero-in-degree removal |
| Cycle detection | Gray state back edge | Emitted count < total |
| Recursion | Yes (or explicit stack) | No, naturally iterative |
| Lex-smallest order | Not straightforward | Use PriorityQueue |

What are common mistakes?

The most common mistake is using a single boolean visited array instead of three colors, which cannot distinguish a back edge (cycle) from a cross edge (safe). Another mistake is forgetting to reverse the post-order.

// Wrong: single visited flag cannot detect cycles correctly
if (visited[v]) continue; // may skip a real cycle

// Correct: three colors distinguish in-progress from finished
if (color[v] == GRAY) throw new IllegalStateException("Cycle");

What about deep graphs and stack overflow?

For very deep graphs the recursion can overflow the call stack. Convert to an iterative DFS using an explicit stack to avoid this. Kahn's algorithm is naturally iterative and avoids this concern entirely.

What should a senior engineer know?

A senior engineer knows that the DFS approach can produce different valid orderings depending on the traversal order of successors, and that neither DFS nor Kahn's guarantees a unique order for a general DAG. The senior also knows that DFS topological sort is the basis for strongly connected component algorithms like Tarjan's and Kosaraju's.