Topo sort and cycle detection

Implement Kahn's algorithm with cycle detection, and DFS-based 3-colour cycle marking for directed graphs.

The previous lesson described both algorithms conceptually. Here we implement them and add the cycle-detection logic that makes them useful in practice.

Kahn's algorithm with cycle detection

Python — editable, runs in your browser

from collections import deque

def kahn_topo_sort(graph):
  """
  Returns (order, has_cycle).
  order     = topological ordering (empty if cycle detected)
  has_cycle = True if the graph contains a directed cycle
  """
  # Count in-degrees
  in_degree = {u: 0 for u in graph}
  for u in graph:
      for v in graph[u]:
          in_degree[v] = in_degree.get(v, 0) + 1
  # Ensure every node appears in in_degree
  for u in graph:
      if u not in in_degree:
          in_degree[u] = 0

queue = deque([u for u in in_degree if in_degree[u] == 0])
  order = []

while queue:
      u = queue.popleft()
      order.append(u)
      for v in graph.get(u, []):
          in_degree[v] -= 1
          if in_degree[v] == 0:
              queue.append(v)

has_cycle = len(order) != len(in_degree)
  return order, has_cycle

# ── 3-colour DFS cycle detection ─────────────────────────────────────────────
# WHITE = unvisited, GREY = in current DFS stack, BLACK = fully processed.
# A back edge (edge to a GREY node) indicates a cycle.

def has_cycle_directed(graph):
  WHITE, GREY, BLACK = 0, 1, 2
  color = {u: WHITE for u in graph}

def dfs(u):
      color[u] = GREY
      for v in graph[u]:
          if color.get(v, WHITE) == GREY:   # back edge found
              return True
          if color.get(v, WHITE) == WHITE:
              if dfs(v):
                  return True
      color[u] = BLACK
      return False

for u in graph:
      if color[u] == WHITE:
          if dfs(u):
              return True
  return False

# ── Tests ─────────────────────────────────────────────────────────────────────
dag = {0: [1, 2], 1: [3], 2: [3], 3: []}
order, cycle = kahn_topo_sort(dag)
print("DAG order:", order)          # [0, 1, 2, 3] or [0, 2, 1, 3]
print("DAG has cycle:", cycle)      # False

cyclic = {0: [1], 1: [2], 2: [0]}
order, cycle = kahn_topo_sort(cyclic)
print("Cyclic order:", order)       # []
print("Cyclic has cycle:", cycle)   # True

print()
print("3-colour: DAG →", has_cycle_directed(dag))       # False
print("3-colour: cyclic →", has_cycle_directed(cyclic)) # True

# Self-loop
self_loop = {0: [0], 1: []}
print("Self-loop →", has_cycle_directed(self_loop))     # True

How Kahn's detects cycles

When a cycle exists, none of the nodes in the cycle ever reach in-degree 0 (each always has at least one incoming edge from another cycle member). They are never enqueued. The output therefore contains fewer nodes than the full graph. The check len(order) != len(in_degree) catches this in O(1) after the algorithm finishes.

How 3-colour DFS detects cycles

Each node carries a colour:

WHITE — not yet visited.
GREY — currently on the DFS call stack (we entered but have not finished exploring its descendants).
BLACK — fully processed; all descendants are done.

When DFS visits a neighbour that is already GREY, we have found a back edge — a path that leads back to an ancestor in the current stack. That is exactly a cycle. A BLACK neighbour is safe: it was fully explored in an earlier DFS tree and cannot form a new cycle through the current path.

3-colour marking is also the standard approach in many compilers and dependency-resolution engines. The colours map directly to "unvisited", "in progress", and "done" states in iterative implementations, where you push a node twice onto an explicit stack — once to enter (mark grey), once to finish (mark black).

Where to go next

Next: lab — graph algorithms — three problems that put Dijkstra's and topological sort to work: network delay time, course schedule ordering, and a course-prerequisite cycle check.

Finished reading? Mark it complete to track your progress.

Topo sort and cycle detection

Kahn's algorithm with cycle detection

How Kahn's detects cycles

How 3-colour DFS detects cycles

Where to go next

On this page