Skills101

AdvancedData Structures & Algorithms · Lesson 29 of 29 · Updated ·

Topological Sort — Kahn's BFS, DFS Order, Cycle Detection and Course Schedule

Your college says: take C before Data Structures, Maths before Data Structures, Data Structures before Algorithms and Operating Systems, and C before DBMS. In what order can you take the courses? Build systems (which file to compile first), package managers (which library to install first) and spreadsheet formulas (which cell to compute first) all ask the same question. The answer is a topological sort.

1. The problem

Model each task as a node and each rule "u must come before v" as a directed edge u → v. A topological order lists all nodes so that every edge points forward (u appears before v).

Course graph: Maths and C have no prerequisites (in-degree 0); DS needs C and Maths (in-degree 2); Algo needs DS and Maths; OS needs DS; DBMS needs C

Two facts to remember:

  • An order exists only if the graph has no cycle. If A needs B and B needs A, nobody can start. A directed graph with no cycle is called a DAG (directed acyclic graph).
  • The order is usually not unique. Maths and C can be taken in either order.

2. Kahn's algorithm (BFS with in-degrees)

The in-degree of a node is the number of edges coming into it — its number of unfinished prerequisites.

  1. Compute every in-degree. Put all nodes with in-degree 0 in a queue.
  2. Take a node from the queue and add it to the answer.
  3. "Remove" its outgoing edges: lower the in-degree of each neighbour by 1. Any neighbour that drops to 0 joins the queue.
  4. Repeat until the queue is empty.

Kahn's algorithm on the course graph, step by step: start with Maths and C in the queue; taking C frees DS and DBMS; taking DS frees Algo and OS; final order Maths, C, DS, DBMS, Algo, OS

Cycle check for free: if the answer has fewer nodes than the graph, some nodes never reached in-degree 0. They are stuck in (or behind) a cycle.

from collections import deque

def topo_kahn(nodes, edges):
    adj = {n: [] for n in nodes}
    indeg = {n: 0 for n in nodes}
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(n for n in nodes if indeg[n] == 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) == len(nodes) else None   # None = cycle

courses = ["Maths", "C", "DS", "DBMS", "Algo", "OS"]
rules = [("C", "DS"), ("Maths", "DS"), ("DS", "Algo"),
         ("Maths", "Algo"), ("C", "DBMS"), ("DS", "OS")]
print(topo_kahn(courses, rules))
print(topo_kahn(["A", "B", "C"], [("A", "B"), ("B", "C"), ("C", "B")]))
['Maths', 'C', 'DS', 'DBMS', 'Algo', 'OS']
None

Time is O(V + E): each node enters the queue once and each edge is looked at once. If you need the smallest order in dictionary order, replace the queue with a min-heap.

3. The DFS method

Run DFS. When a node finishes (all its descendants are done), push it onto a list. The reverse of the finishing order is a topological order — a node finishes only after everything that depends on it has finished.

To detect a cycle, give each node one of three colours:

ColourMeaning
white (0)not visited yet
gray (1)on the current DFS path, still in progress
black (2)finished

Reaching a gray node means we came back to a node on our own path: that is a cycle. Reaching a black node is fine — it is just a shared prerequisite.

import sys
sys.setrecursionlimit(10000)

def topo_dfs(nodes, edges):
    adj = {n: [] for n in nodes}
    for u, v in edges:
        adj[u].append(v)
    color = {n: 0 for n in nodes}
    out = []
    def dfs(u):
        color[u] = 1
        for v in adj[u]:
            if color[v] == 1:
                return False                 # back edge: cycle
            if color[v] == 0 and not dfs(v):
                return False
        color[u] = 2
        out.append(u)                        # u is finished
        return True
    for n in nodes:
        if color[n] == 0 and not dfs(n):
            return None
    return out[::-1]

courses = ["Maths", "C", "DS", "DBMS", "Algo", "OS"]
rules = [("C", "DS"), ("Maths", "DS"), ("DS", "Algo"),
         ("Maths", "Algo"), ("C", "DBMS"), ("DS", "OS")]
print(topo_dfs(courses, rules))
['C', 'DBMS', 'Maths', 'DS', 'OS', 'Algo']

This is a different order from Kahn's, and it is also correct: check that every rule points forward.

4. Course schedule in Java

The classic interview version: n courses numbered 0..n−1 and pairs [a, b] meaning "to take a, first take b". Can you finish all courses? (Course Schedule I.) Return one valid order. (Course Schedule II.) Both are Kahn's algorithm; note the edge goes b → a.

import java.util.*;

public class Main {
    static int[] findOrder(int n, int[][] prereq) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] p : prereq) {          // p = {course, needs}
            adj.get(p[1]).add(p[0]);
            indeg[p[0]]++;
        }
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i);
        int[] order = new int[n];
        int k = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            order[k++] = u;
            for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
        }
        return k == n ? order : new int[0];   // empty = impossible
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
        System.out.println(Arrays.toString(findOrder(2, new int[][]{{1, 0}, {0, 1}})));
    }
}
[0, 1, 2, 3]
[]

5. Where topological order helps

  • Scheduling with dependencies: courses, build steps, project tasks.
  • DP on a DAG: longest path, number of paths, or earliest finish time. Process nodes in topological order so every node's inputs are ready. Longest path in a general graph is very hard, but on a DAG it is O(V + E).
  • Alien dictionary: compare neighbouring words to get "letter x comes before letter y" edges, then topologically sort the letters.

Common mistakes

  • Reversing the edge direction for course pairs. [a, b] = "a needs b" = edge b → a.
  • Forgetting the cycle check: Kahn's must compare len(order) with the number of nodes.
  • In DFS cycle detection, using only visited/not-visited. A visited (black) node is not a cycle; only a gray one is.
  • Forgetting nodes with no edges at all. They have in-degree 0 and belong in the answer.
  • Returning the DFS finishing order without reversing it.

Quick recap

  • Topological order: every edge u → v has u before v. It exists only for a DAG and is often not unique.
  • Kahn's: queue the in-degree-0 nodes, remove them one by one, lowering neighbours' in-degrees.
  • DFS: reverse of finishing order; a gray node reached again means a cycle.
  • Both run in O(V + E). Fewer nodes in the output than in the graph means a cycle.

Practice what you learned

📝 Quiz: Topological Sort5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →