Topological Sort

Kahn's Algorithm (BFS)

Find all nodes with 0 incoming edges (no dependencies). Process them, remove their outgoing edges (decrement neighbors' in-degrees). Repeat. If all nodes are processed, you have a valid order. If not, there's a cycle.

O(V + E)

O(V)

say this out loud

Dependencies, so topological order. I repeatedly take nodes with in-degree zero, and if I cannot empty the graph there is a cycle.

How It Works

Kahn's algorithm produces a topological order of a DAG using in-degrees. First compute each node's in-degree (number of incoming edges) and enqueue every node with in-degree 0. These have no unmet dependencies. Repeatedly dequeue a node, append it to the order, and decrement the in-degree of each neighbor; any neighbor that drops to 0 joins the queue. The invariant is that a node is only emitted once all of its prerequisites have been emitted.

The algorithm runs in O(V + E) since every node is enqueued once and every edge decrements exactly one counter. It also doubles as a cycle detector: nodes on a cycle never reach in-degree 0, so if the output contains fewer than V nodes, the graph has a cycle and no valid ordering exists.

Step-by-Step Visualization

Edges 0->2, 1->2, 2->3. in-degree counts how many prerequisites each node has

in-degree[0, 0, 2, 1]

queue[0, 1]

1/5

Code

Java

static int[] topologicalSort(int[][] graph, int n) {
  int[] inDeg = new int[n];
  for (int[] e : graph) inDeg[e[1]]++;

  Queue<Integer> queue = new LinkedList<>();
  for (int i = 0; i < n; i++) if (inDeg[i] == 0) queue.add(i);

  List<Integer> order = new ArrayList<>();
  while (!queue.isEmpty()) {
    int node = queue.poll();
    order.add(node);
    for (int[] e : graph) {
      if (e[0] == node && --inDeg[e[1]] == 0) queue.add(e[1]);
    }
  }

  return order.size() == n ? order.stream().mapToInt(Integer::intValue).toArray() : new int[]{};
}

Tips & Gotchas

1Start with all nodes that have 0 in-degree (no dependencies)

2Process them, reduce in-degree of their neighbors

3If processed count < V, there's a cycle (impossible to sort)

Practice Problems

1Course Schedule
2Course Schedule II
3Alien Dictionary
4Minimum Height Trees
5Parallel Courses

About the Topological Sort Pattern

Order the nodes of a directed graph so that for every edge A→B, A comes before B. Only works on DAGs (directed acyclic graphs). If a cycle exists, topological sort is impossible, which is how you detect cycles.

Key insight

Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.

Common Graphs Interview Problems

Number of Islands
Clone Graph
Course Schedule
Pacific Atlantic Water Flow
Network Delay Time
Minimum Spanning Tree
Word Ladder

Frequently Asked Questions

Should I use Kahn's algorithm or DFS post-order for topological sort?

Both are O(V + E) and equally valid; Kahn's is often preferred in interviews because cycle detection falls out for free from counting processed nodes, and the queue-based code avoids recursion depth issues. Kahn's also naturally supports level-by-level processing, useful for questions like minimum semesters needed.

What happens if the graph has a cycle?

Nodes inside the cycle keep positive in-degree because each waits on another cycle member, so they never enter the queue. You detect this by comparing the count of emitted nodes to V, a shortfall means a cycle exists and the problem instance (like a course schedule) is unsatisfiable.

Is the topological order unique?

Rarely. Any moment the queue holds more than one zero in-degree node, multiple valid orders exist. If a problem needs a specific one, such as lexicographically smallest, replace the queue with a min-heap.