Algorithm Visualizations — Graph Algorithms

Topological Sort

Kahn's algorithm, step by step. Peel off the nodes with no prerequisites, one at a time, and watch the dependency graph collapse into a linear ordering.

LeetCode #207 · Course Schedule · BFS + In-degree

Given numCourses and a list of prerequisite pairs [a, b] meaning "to take course a you must first take course b", determine whether it's possible to finish all courses.

A valid schedule exists if and only if the prerequisite graph is a DAG (no cycles). Kahn's algorithm produces a valid topological order by repeatedly picking a node with zero remaining prerequisites. If every node eventually makes it out, no cycle exists.

Cycle detection

If Kahn's finishes with fewer than n nodes in the order, the leftover nodes are stuck in a cycle — each one waits on another whose in-degree will never reach zero. Return false.

Core Idea

A node can be taken as soon as all of its prerequisites are done. Kahn's tracks that by keeping an in-degree counter per node and a queue of nodes whose counter has dropped to zero.

Kahn's Algorithm

in_deg = count incoming edges
queue  = [n for n in nodes if in_deg[n] == 0]
while queue:
  u = queue.popleft()
  order.append(u)
  for v in adj[u]:
    in_deg[v] -= 1
    if in_deg[v] == 0:
      queue.append(v)

Compute in-degree for every node. Nodes with in-degree 0 have no prerequisites and are ready to take.

Step 1 / 21

Blocked (in-degree > 0)

In queue (ready)

Processing

Done

Edge being removed

Queue (FIFO)

Topological Order

time: O(V + E) space: O(V + E) pattern: BFS + in-degree

Implementation Notes

Key Insight: A node is safe to process once every incoming edge has been removed — i.e. every prerequisite has already been handled. The in-degree counter is exactly "how many prerequisites remain."
Cycle Check: If the final order contains fewer than n nodes, at least one cycle exists. The stranded nodes form the cycle (or sit downstream of it).
Edge Direction: For LC #207, prerequisite pair [a, b] means b → a (take b before a). In-degree of a counts how many courses must be finished before a can be taken.
Time: O(V + E) — each node enqueued once, each edge scanned once
Space: O(V + E) for adjacency list + O(V) for in-degree + queue
DFS Alternative: Topological sort can also be done via DFS post-order with a three-color cycle check (white/gray/black). Kahn's tends to be simpler for interview settings.
Non-uniqueness: A DAG can have many valid topological orders. The queue's tie-breaking (FIFO here) picks one of them.