11.2 Topological Sort & Directed Cycle Detection

1. What Is Topological Sort?

Suppose you are registering for university classes or building software packages where Task A must be finished before Task B can start (A -> B). A Topological Sort takes a Directed Graph and lines up all nodes in a valid sequence [u1, u2, ..., uN] such that for every directed arrow A -> B, A appears before B.

(Note: If the graph has a directed cycle like A -> B -> A, a valid ordering is impossible! A directed graph with no cycles is called a DAG — Directed Acyclic Graph.)

2. Why Do We Need It & How Does Kahn's Indegree Algorithm Work?

What Is indegree?

The indegree of a node v is simply how many prerequisites (incoming arrows) v is still waiting on.

• If indegree[v] == 0, node v has zero unmet prerequisites — it is ready to take right now!

Kahn's BFS Algorithm in 4 Simple Steps

1. Build the directed adjacency list adj[pre].append(course) and count indegree[course] += 1.
2. Push every node with indegree == 0 into a FIFO Queue.
3. While the queue is not empty: pop u, add u to your order list, and for each neighbor v in adj[u], subtract 1 from indegree[v] (because prerequisite u is now done!). The moment indegree[v] == 0, push v into the queue!
4. At the end, check len(order) == n: if fewer than n nodes were processed, a cycle locked the remaining nodes!

Alternative Approach: 3-Color DFS Cycle Detection (0 = Unvisited, 1 = Visiting, 2 = Done)

Besides Kahn's BFS, interviewers also love asking how to detect a cycle in a Directed Graph using recursion (DFS):

• Why isn't a normal visited set enough for directed graphs? Because if A -> C and B -> C, visiting C twice from two different branches is not a cycle!
• A cycle only happens if you run into a node that is currently still on your active recursion stack!
• Track state[u]:
  • 0 (Unvisited): Haven't touched u yet.
  • 1 (Visiting / On Current Path): Currently exploring u's descendants. If you see an edge to a node with state == 1, you found a back-edge cycle!
  • 2 (Completed / Safe): Finished exploring u and all its descendants with zero cycles; future visits can skip u in O(1).

3. Basic Operations & Walkthroughs (All 4 Languages)

from collections import deque

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
  adj = [[] for _ in range(num_courses)]
  indegree = [0] * num_courses
  for course, pre in prerequisites:
      adj[pre].append(course)
      indegree[course] += 1

  # Start with all courses that have 0 prerequisites
  q = deque([i for i in range(num_courses) if indegree[i] == 0])
  completed = 0

  while q:
      curr = q.popleft()
      completed += 1
      for nxt in adj[curr]:
          indegree[nxt] -= 1
          if indegree[nxt] == 0:
              q.append(nxt)

  return completed == num_courses

4. Core Interview Patterns & Common Traps

q = deque([u for u in range(n) if indegree[u] == 0])
order = []
while q:
  u = q.popleft()
  order.append(u)
  for v in adj[u]:
      indegree[v] -= 1
      if indegree[v] == 0:
          q.append(v)
return order if len(order) == n else []  # Empty if a cycle exists!

5. Practice On Your Own (Curated Submodule Problems)