Topological Sort: Kahn's Algorithm, DFS Order & the Interview Problems That Use Them

Any time a problem says "prerequisite", "depends on", "must happen before", "build order" or "compile order", you are being asked for a topological sort. It is one of the highest-yield graph topics for interviews because the code is short, the problems disguise it well, and it doubles as directed cycle detection.

This guide builds both algorithms carefully, then works through the problem families with complete code, including the two that trip people up most: Alien Dictionary's edge cases and "minimum time to finish all tasks".

What a Topological Order Means (and When It Exists)

Take a directed graph where an edge u → v means "u must come before v". A topological order is a permutation of all vertices in which every edge goes from left to right.

Two facts to state confidently in an interview:

• A topological order exists if and only if the graph has no directed cycle. If A → B → C → A, then A must come before itself. Conversely, every DAG has at least one vertex with in-degree 0 (otherwise you could walk backwards forever and would have to repeat a vertex, forming a cycle). Remove it, and the rest is still a DAG; repeat. That argument is literally Kahn's algorithm.
• The order is usually not unique. Any two vertices with no path between them can appear in either order.

Kahn's Algorithm: Topological Sort with BFS and In-Degrees

1. Compute in-degrees. For each edge u → v, increment indeg[v].
2. Seed the queue with every vertex whose in-degree is 0: no prerequisites.
3. Process. Pop u, append it to the order, and for each edge u → v decrement indeg[v]; if it hits 0, push v.
4. Check. If the order has V vertices, it is a valid topological order. Otherwise the remaining vertices are on, or depend on, a cycle.

// Returns a topological order, or an empty array if the graph has a cycle.
int[] topoSortKahn(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        indeg[e[1]]++;
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int v = 0; v < n; v++) if (indeg[v] == 0) queue.offer(v);

    int[] order = new int[n];
    int idx = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order[idx++] = u;
        for (int v : adj.get(u)) {
            if (--indeg[v] == 0) queue.offer(v);
        }
    }
    return idx == n ? order : new int[0];
}

vector<int> topoSortKahn(int n, const vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);
    for (auto [u, v] : edges) {
        adj[u].push_back(v);
        indeg[v]++;
    }
    queue<int> q;
    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.push(v);
    vector<int> order;
    order.reserve(n);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);
    }
    if ((int)order.size() != n) return {};   // cycle
    return order;
}

from collections import deque

def topo_sort_kahn(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []

Dry run on the graph above (edges 5→2, 5→0, 4→0, 4→1, 2→3, 3→1):

All six vertices were output, so there is no cycle. Every edge points forward: 5 (pos 1) → 2 (pos 2), 2 → 3, 3 → 1, 4 → 0, 4 → 1, 5 → 0. Each vertex enters the queue once and each edge decrements one counter once, so the time is O(V + E) and extra space O(V) beyond the graph.

The queue type does not affect correctness. A stack also works; a min-heap gives the lexicographically smallest order (more on that below).

Topological Sort with DFS: Reverse Post-Order

Run DFS; when a vertex finishes (all its descendants are done), append it to a list. Reverse the list at the end.

Why it works: take any edge u → v. When DFS examines this edge from u, v is either unvisited (then DFS visits v and v finishes before u), or finished already (v finished before u), or on the current stack (a back edge, which means a cycle, which we report). In every acyclic case, v finishes before u, so in the reversed finish order u comes before v. That is the whole proof.

class TopoDFS {
    private List<List<Integer>> adj;
    private int[] state;                 // 0 = unvisited, 1 = on stack, 2 = done
    private List<Integer> post = new ArrayList<>();
    private boolean hasCycle = false;

    List<Integer> sort(int n, List<List<Integer>> adj) {
        this.adj = adj;
        state = new int[n];
        for (int v = 0; v < n && !hasCycle; v++)
            if (state[v] == 0) dfs(v);
        if (hasCycle) return Collections.emptyList();
        Collections.reverse(post);
        return post;
    }

    private void dfs(int u) {
        state[u] = 1;
        for (int v : adj.get(u)) {
            if (state[v] == 1) { hasCycle = true; return; }
            if (state[v] == 0) {
                dfs(v);
                if (hasCycle) return;
            }
        }
        state[u] = 2;
        post.add(u);                     // u finishes after all its descendants
    }
}

import sys

def topo_sort_dfs(n, adj):
    sys.setrecursionlimit(max(1000, 2 * n + 10))
    state = [0] * n                     # 0 white, 1 gray, 2 black
    post = []

    def dfs(u):
        state[u] = 1
        for v in adj[u]:
            if state[v] == 1:
                return False            # back edge: cycle
            if state[v] == 0 and not dfs(v):
                return False
        state[u] = 2
        post.append(u)
        return True

    for v in range(n):
        if state[v] == 0 and not dfs(v):
            return []
    return post[::-1]

A common wrong version uses a single boolean visited array and appends nodes in pre-order. Pre-order is not a topological order: in the graph A → B, A → C, C → B, pre-order from A could be A, B, C, which puts B before C despite C → B. Post-order reversed gives A, C, B. Correct.

Kahn's Algorithm vs DFS: Which to Use

My advice: default to Kahn's. It handles the follow-ups (levels, smallest order, cycle participants) with one-line changes, and it avoids recursion limits. Learn DFS too because the "reverse post-order" idea reappears in Kosaraju's strongly connected components algorithm, and some interviewers will ask for it specifically.

Course Schedule I and II: The Canonical Problems

Course Schedule (207) gives numCourses and prerequisites[i] = [a, b] meaning "to take a you must first take b". Can you finish all courses? That is "is the graph acyclic?". Note the edge direction: b → a. Getting it backwards still detects cycles correctly (reversing every edge preserves cycles), but in Course Schedule II it reverses the output order.

Course Schedule II (210) asks for an actual order. With Kahn's algorithm, both are the same code: return len(order) == n for 207 and order for 210.

from collections import deque

def find_order(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for course, pre in prerequisites:
        adj[pre].append(course)          # pre must come before course
        indeg[course] += 1
    q = deque(c for c in range(num_courses) if indeg[c] == 0)
    order = []
    while q:
        c = q.popleft()
        order.append(c)
        for nxt in adj[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return order if len(order) == num_courses else []

A full walkthrough with diagrams and the DFS version is in LeetCode 207 Course Schedule explained. Related: Course Schedule IV (1462) answers many "is a a prerequisite of b?" queries; precompute reachability for each node by propagating ancestor sets in topological order, or with Floyd-Warshall-style transitive closure for n ≤ 100.

Alien Dictionary: Build the Graph, Then Sort

Alien Dictionary (LeetCode 269, premium; also on GeeksforGeeks) gives words sorted in an unknown alphabet and asks for a valid letter order. It is a favourite at Google, Meta, Airbnb and several Indian product companies because the topological sort is easy, but building the graph has edge cases.

Building edges from adjacent words

Only adjacent pairs matter (non-adjacent comparisons are implied by transitivity). For each pair, find the first position where they differ: that gives one edge w1[j] → w2[j]. Characters after that position tell you nothing.

Edge cases:

• Prefix violation: if w1 is longer than w2 and w2 is a prefix of w1 (for example "abc" before "ab"), the input is invalid. Return "".
• Letters with no edges still belong in the output. Add every character that appears in any word as a vertex.
• Duplicate edges (the same pair inferred twice) would double-count in-degrees. Use a set of neighbours.
• Cycle means contradictory ordering. Return "".

from collections import deque

def alien_order(words):
    adj = {c: set() for w in words for c in w}
    indeg = {c: 0 for c in adj}
    for w1, w2 in zip(words, words[1:]):
        for a, b in zip(w1, w2):
            if a != b:
                if b not in adj[a]:
                    adj[a].add(b)
                    indeg[b] += 1
                break
        else:                                   # no differing position found
            if len(w1) > len(w2):
                return ""                       # "abc" before "ab" is invalid
    q = deque(c for c in indeg if indeg[c] == 0)
    out = []
    while q:
        c = q.popleft()
        out.append(c)
        for nxt in adj[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return "".join(out) if len(out) == len(adj) else ""

public String alienOrder(String[] words) {
    Map<Character, Set<Character>> adj = new HashMap<>();
    Map<Character, Integer> indeg = new HashMap<>();
    for (String w : words)
        for (char c : w.toCharArray()) {
            adj.putIfAbsent(c, new HashSet<>());
            indeg.putIfAbsent(c, 0);
        }
    for (int i = 0; i + 1 < words.length; i++) {
        String a = words[i], b = words[i + 1];
        if (a.length() > b.length() && a.startsWith(b)) return "";
        for (int j = 0; j < Math.min(a.length(), b.length()); j++) {
            char x = a.charAt(j), y = b.charAt(j);
            if (x != y) {
                if (adj.get(x).add(y)) indeg.merge(y, 1, Integer::sum);
                break;
            }
        }
    }
    Deque<Character> q = new ArrayDeque<>();
    for (Map.Entry<Character, Integer> e : indeg.entrySet())
        if (e.getValue() == 0) q.offer(e.getKey());
    StringBuilder sb = new StringBuilder();
    while (!q.isEmpty()) {
        char c = q.poll();
        sb.append(c);
        for (char nxt : adj.get(c))
            if (indeg.merge(nxt, -1, Integer::sum) == 0) q.offer(nxt);
    }
    return sb.length() == adj.size() ? sb.toString() : "";
}

Dry run with ["wrt", "wrf", "er", "ett", "rftt"]: the pairs give t → f (wrt/wrf), w → e (wrf/er), r → t (er/ett), e → r (ett/rftt). Only w has in-degree 0, and the chain unwinds as w, e, r, t, f. Output "wertf". Complexity: O(C) to scan all characters across words (C = total length), plus O(U + E) for the sort where U ≤ 26 letters and E ≤ number of adjacent pairs.

Levels, Minimum Semesters and the Critical Path

Parallel Courses (1136): minimum number of semesters

If you can take any number of courses per semester as long as prerequisites are done, the answer is the number of BFS layers in Kahn's algorithm: process the queue one level at a time and count levels. Return −1 if not all courses are processed. This is the longest path (in edges) through the DAG, plus one.

Parallel Courses III (2050): courses have durations

Now each course takes time[i] months and unlimited courses run in parallel. The earliest finish of course v is time[v] + max(finish[u] for u → v). Compute it in topological order; the answer is the maximum finish time. This is the critical path, the same calculation project managers use, and it is a longest-path problem that is easy precisely because the graph is a DAG.

int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0), finish(n, 0);
    for (auto& r : relations) {              // 1-indexed: r[0] before r[1]
        adj[r[0] - 1].push_back(r[1] - 1);
        indeg[r[1] - 1]++;
    }
    queue<int> q;
    for (int v = 0; v < n; v++)
        if (indeg[v] == 0) { q.push(v); finish[v] = time[v]; }
    int ans = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ans = max(ans, finish[u]);
        for (int v : adj[u]) {
            finish[v] = max(finish[v], finish[u] + time[v]);
            if (--indeg[v] == 0) q.push(v);
        }
    }
    return ans;
}

Why does finish[v] become correct? By the time v is popped, all its predecessors have been popped and each has contributed finish[u] + time[v], so the max is over all of them. The same "DP in topological order" idea gives shortest paths on DAGs with negative weights, as mentioned in the shortest path algorithms guide, and counts the number of paths between two nodes.

Unique, Lexicographically Smallest and All Topological Orders

Is the topological order unique? (Sequence Reconstruction, 444)

The order is unique if and only if Kahn's queue never contains more than one vertex. If at any moment two vertices both have in-degree 0, they can be swapped. In code, check len(q) > 1 at the top of the loop and return false. Equivalently, every consecutive pair in the order must be joined by an edge.

Lexicographically smallest order

Replace the queue with a min-heap. At each step you output the smallest available vertex, which is a greedy choice that is provably optimal for lexicographic order. Complexity becomes O(V log V + E).

import heapq

def smallest_topo_order(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    heap = [v for v in range(n) if indeg[v] == 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 []

All topological orders

Backtracking over Kahn's choices: at each step, try every vertex with in-degree 0 that is not yet used, decrement its neighbours, recurse, then undo. The number of orders can be V! (no edges at all), so this is only feasible for small graphs. It is a good bridge to the backtracking template: choose, explore, un-choose.

Where Topological Sort Runs in Real Systems

Interviewers like candidates who connect algorithms to systems. Topological ordering shows up everywhere dependencies exist:

In a system design discussion or a machine coding round where you build a task scheduler or job runner, mentioning "I'll validate the job graph with Kahn's algorithm and run each level in parallel" is a strong, concrete design choice.

How Topological Sort Shows Up in Interviews

Topological sort rarely appears by name. The skill being tested is recognising dependencies and modelling edges in the right direction. Expect this flow:

1. Recognition. Say: "These are dependencies, so this is a directed graph; I need an order consistent with all of them, so topological sort."
2. Edge direction. Say explicitly which way edges point and why. "Prerequisite b before course a, so edge b → a."
3. Cycle handling. State what you return when there is a cycle before you write code.
4. Follow-up 1: "Can you print which courses are blocked by the cycle?" With Kahn's, any vertex with remaining in-degree > 0.
5. Follow-up 2: "Minimum semesters if you can take at most K per semester?" (Parallel Courses II, 1494) That one is NP-hard in general and solved with bitmask DP for n ≤ 15; recognising that greedy by level fails here is the point of the question.
6. Follow-up 3: "Dependencies arrive one at a time; detect the first one that creates a cycle." Incremental cycle detection; for small inputs re-run, or check reachability from v to u before adding u → v.

For undirected "does adding this edge create a cycle" questions, the right tool is different: union-find. Knowing which applies to directed versus undirected graphs is itself an interview signal.

Common Topological Sort Mistakes

• Reversed edges in prerequisite problems, producing an order that is exactly backwards.
• Pre-order instead of reversed post-order in the DFS version.
• Two-state visited in DFS cycle detection: a node visited in an earlier, finished branch is not a cycle. You need three states.
• Double-counting in-degrees from duplicate edges (Alien Dictionary). Deduplicate with a set.
• Missing isolated vertices: a course with no prerequisites and no dependents still belongs in the order. Seed from all V vertices, not just those appearing in edges.
• Applying topological sort to an undirected graph. It is undefined; use union-find or DFS with a parent check for cycles.

Topological Sort Practice List

Minimum Height Trees deserves a note: it applies the in-degree-peeling idea to an undirected tree by repeatedly removing leaves (degree 1). The last one or two remaining nodes are the centroids. It shows that Kahn's algorithm is really a general "peel from the outside" technique. For where this topic fits in a full preparation plan, see the top DSA patterns for coding interviews.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.