Topological Sort

Imagine a city map where every road is one-way, and there are no circular routes. This is a Directed Acyclic Graph (DAG) (stored as a graph). You want to list all the cities in an order such that every one-way road goes from an earlier city to a later one in your list.

That ordering is called a topological sort. It's the answer to: "What's a valid order to do things when some tasks must come before others?" — like course prerequisites, build dependencies, or assembly steps.

Kahn's Algorithm (BFS-based)

The key insight: a city with no incoming roads (in-degree = 0) can go first — nothing needs to happen before it. Remove it, and some neighbors may now have no incoming roads either. Repeat.

pseudocode

function kahnSort(graph):
  inDegree = count incoming edges for each city
  queue = all cities with inDegree 0
  order = []

  while queue not empty:
    city = queue.shift()
    order.push(city)
    for neighbor of graph[city]:
      inDegree[neighbor]--
      if inDegree[neighbor] === 0:
        queue.push(neighbor)

  // If order.length < V, there was a cycle!
  return order

DFS-based Algorithm

Run DFS. When a city is fully explored (all its outgoing roads have been followed), push it onto a stack. At the end, pop the stack to get the topological order. Cities finished last go to the front — they have no dependencies after them.

pseudocode

function dfsTopoSort(graph):
  visited = {}
  stack = []

  function dfs(city):
    visited[city] = true
    for neighbor of graph[city]:
      if not visited[neighbor]: dfs(neighbor)
    stack.push(city)  // push after all descendants are done

  for each city: if not visited: dfs(city)
  return stack.reverse()

Cycle detection bonus

Kahn's algorithm doubles as a cycle detector: if the output has fewer than V cities, some cities had non-zero in-degree even after processing everything reachable — they're part of a cycle, making topological sort impossible.

Topological Sort (Kahn's Algorithm)

from collections import deque

def topo_sort(n, edges):
    """Kahn's BFS-based topological sort."""
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == n else []  # empty = cycle

# DAG: 5->0, 5->2, 4->0, 4->1, 2->3, 3->1
print(topo_sort(6, [(5,0),(5,2),(4,0),(4,1),(2,3),(3,1)]))
# [4, 5, 0, 2, 3, 1]  (one valid order)

Output

[4, 5, 0, 2, 3, 1]

Course Schedule (Cycle Detection)

from collections import deque

def can_finish(num_courses, prerequisites):
    """Return True if all courses can be completed (no cycle)."""
    graph = [[] for _ in range(num_courses)]
    in_degree = [0] * num_courses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    q = deque(i for i in range(num_courses) if in_degree[i] == 0)
    done = 0
    while q:
        node = q.popleft(); done += 1
        for nb in graph[node]:
            in_degree[nb] -= 1
            if in_degree[nb] == 0: q.append(nb)
    return done == num_courses

print(can_finish(2, [[1,0]]))         # True  (0 -> 1)
print(can_finish(2, [[1,0],[0,1]]))   # False (cycle)