Advanced Topological Sort — DFS, Kahn's, Lexicographic, Parallel Scheduling [LC 210, Google, Amazon]

Problem Statement#

Given a directed graph with n vertices, return a linear ordering of the vertices such that for every directed edge u -> v, vertex u comes before v in the ordering. If the graph has a cycle, no valid topological order exists. Beyond the basic problem, advanced versions ask for the lexicographically smallest order, the maximum parallel level ordering (level by level), or for all valid orderings.

Constraints:

• 1 <= n <= 10^5
• 0 <= m <= 10^5
• The graph must be a DAG for an ordering to exist.

Example:

Input:  n = 6, edges = [[5,2],[5,0],[4,0],[4,1],[2,3],[3,1]]
Output: One valid topo order = [4, 5, 2, 3, 1, 0]
        Lexicographically smallest = [4, 5, 0, 2, 3, 1]

Why This Problem Matters#

Topological sort underlies almost every dependency-resolution system in production software: build systems (make, bazel, cargo), package managers (npm, pip), task schedulers (Airflow, Celery), Excel formula recomputation, and React's component update order. Whenever computations have prerequisites, a topological sort produces the legal execution order.

LeetCode 210 (Course Schedule II), 269 (Alien Dictionary), 444 (Sequence Reconstruction), 802 (Find Eventual Safe States), and 1136 (Parallel Courses) are all topo-sort variants that show up at Google, Amazon, and Meta. Recognising the pattern — "one task must finish before another" — is the single most important skill, and the variant flavour (lex-smallest, parallel-level, unique-order) determines the tweak.

The advanced versions test deeper understanding. Lex-smallest demands a min-heap instead of a queue. Parallel-level demands processing one BFS layer at a time. Detecting whether the order is unique demands checking that the queue never has more than one element. Each twist is a one-line change to a clean Kahn's implementation.

The Core Insight#

There are two canonical algorithms.

Kahn's algorithm (BFS): Compute the in-degree of every vertex. Initialise a queue with all vertices of in-degree 0. Repeatedly pop a vertex, append it to the output, and decrement the in-degree of each of its successors; whenever a successor's in-degree hits 0, push it. After processing, if the output contains all n vertices, you have a valid order; otherwise the graph has a cycle.

DFS post-order: Run DFS. When a vertex finishes (all its descendants have been visited), prepend it to the output. The reversed post-order is a valid topological order. Detect cycles with a three-colour marking: white (unvisited), gray (on stack), black (finished). Encountering a gray vertex during DFS means a back edge — a cycle.

For the lexicographically smallest order, replace Kahn's queue with a min-heap. For parallel level scheduling, process each level in one BFS step and record the level count — that gives the minimum number of semesters or rounds. For uniqueness, check that the queue/heap never contains more than one vertex at any moment.

For all valid orderings, use backtracking: at each step pick any vertex with in-degree 0, mark it, recurse, then unmark.

Visual Dry Run (Kahn's)#

Edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1.

In-degrees: [2, 2, 1, 1, 0, 0] (vertices 0..5).

Output is [4, 5, 1, 2, 0, 3] — a valid topological order. Replacing the FIFO queue with a min-heap would produce the lex-smallest order instead.

Solution (Optimal)#

Python#

from collections import deque, defaultdict
import heapq
 
def kahn_topo(n, edges):
    """Standard Kahn topological sort returning any valid order, or None on cycle."""
    adj = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
 
    queue = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == n else None  # None means cycle exists
 
def lex_smallest_topo(n, edges):
    """Lexicographically smallest topological order using a min-heap."""
    adj = defaultdict(list)
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v); indeg[v] += 1
 
    heap = [i for i in range(n) if indeg[i] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        u = heapq.heappop(heap)
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                heapq.heappush(heap, v)
    return order if len(order) == n else None
 
def min_semesters(n, prerequisites):
    """Minimum levels (parallel courses). Each level processes all currently available tasks."""
    adj = defaultdict(list)
    indeg = [0] * n
    for v, u in prerequisites:  # course u required before v
        adj[u].append(v); indeg[v] += 1
 
    queue = deque(i for i in range(n) if indeg[i] == 0)
    levels = 0
    taken = 0
    while queue:
        levels += 1
        # process the entire current level in one batch
        for _ in range(len(queue)):
            u = queue.popleft()
            taken += 1
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    queue.append(v)
    return levels if taken == n else -1

JavaScript#

function kahnTopo(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    const indeg = new Array(n).fill(0);
    for (const [u, v] of edges) { adj[u].push(v); indeg[v]++; }
 
    const queue = [];
    for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
 
    const order = [];
    let head = 0;
    while (head < queue.length) {
        const u = queue[head++];
        order.push(u);
        for (const v of adj[u]) {
            if (--indeg[v] === 0) queue.push(v);
        }
    }
    return order.length === n ? order : null;
}
 
function dfsTopo(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) adj[u].push(v);
    const color = new Array(n).fill(0); // 0 white, 1 gray, 2 black
    const order = [];
    let cycle = false;
 
    function dfs(u) {
        if (cycle) return;
        color[u] = 1;
        for (const v of adj[u]) {
            if (color[v] === 1) { cycle = true; return; }  // back edge -> cycle
            if (color[v] === 0) dfs(v);
        }
        color[u] = 2;
        order.push(u); // post-order; reverse later
    }
 
    for (let i = 0; i < n && !cycle; i++) if (color[i] === 0) dfs(i);
    return cycle ? null : order.reverse();
}

Complexity: Time O(V + E) for both Kahn's and DFS variants. The lex-smallest variant adds a log factor: O((V + E) log V). Space O(V + E) for adjacency lists.

Common Mistakes#

1. Returning a partial order on a cyclic graph. Always check len(order) == n at the end. If shorter, the remaining vertices form one or more cycles.
2. Confusing in-degree and out-degree. Kahn's uses in-degrees; DFS post-order builds the answer through out-edges. Flipping them silently produces wrong orders.
3. Reversing post-order incorrectly in DFS. Vertices are appended when finished, so the natural list is reverse-topological. Either reverse at the end or use prepend.
4. Using BFS-FIFO when lex-smallest is required. Replace the queue with a min-heap.
5. Treating equal-priority parallel tasks sequentially. When a problem asks for "minimum semesters" or "parallel levels," consume the entire layer before moving to the next.
6. Modifying in-degrees during iteration. Decrement in-degree only when processing an edge; not before queueing.

Interview Tips#

• State up front whether you will use Kahn's or DFS. Kahn's is preferred when the interviewer wants level information or lex-smallest. DFS is preferred when you also need to list cycle members.
• Mention the cycle-detection requirement explicitly. Many candidates forget this.
• For parallel-level questions, explain the "process current queue size" snapshot trick clearly.
• Show how a single line change converts your code from any-order to lex-smallest order. Interviewers love this kind of insight.
• For "is the order unique?" check whether the queue ever contains more than one vertex at the same time.

Follow-up Questions#

1. LeetCode 210 (Course Schedule II): Standard Kahn's — return the order or empty array on cycle.
2. LeetCode 269 (Alien Dictionary): Build the precedence graph from adjacent word comparisons, then topo-sort.
3. LeetCode 444 (Sequence Reconstruction): Topo-sort + uniqueness check.
4. LeetCode 1136 (Parallel Courses): Level-by-level Kahn's; answer is the level count.
5. How to enumerate all valid topological orders? Backtracking: at each step pick any 0-indegree vertex.

Key Takeaways#

• Topological sort linearises a DAG so every edge points forward; impossible if and only if the graph has a cycle.
• Kahn's algorithm uses BFS on in-degree-zero vertices; DFS post-order does it via reverse finish times.
• A min-heap replacing the queue gives the lexicographically smallest valid order.
• Processing each level in one snapshot solves parallel-scheduling problems like LeetCode 1136.
• Detect cycles by checking len(order) != n (Kahn) or by gray-vertex back edges (DFS).
• Topological sort is the workhorse algorithm behind build systems, schedulers, package managers, and Excel — making it one of the most production-relevant graph algorithms.