Graphs

Topological Sort

Order a DAG so every edge points forward; detect cycles in dependencies.

Medium, about 90 minutes to practise.

1Understand

The idea

In a dependency graph, a node can be done once all its prerequisites are done. Count each node's incoming edges, start with the nodes at zero, and every time you finish a node, decrease the count of its successors (Kahn's algorithm). If some nodes never reach zero, there is a cycle.

Intuition

In a dependency graph, a node can be done once all its prerequisites are done. Kahn's algorithm counts incoming edges, starts with nodes at zero, and every time you finish a node, decrease the count of its successors.

If some nodes never reach zero indegree, there is a cycle, the order is impossible. DFS-based topo sort pushes nodes after their descendants and reverses the finish order.

Both produce a valid linear order when the graph is a DAG.

What you will be able to do

  • Implement Kahn's algorithm
  • Detect a cycle from the output length

When to use it

  • Prerequisites / dependencies / build order
  • Can all tasks be completed?
  • Order letters from a sorted alien dictionary

2See it

Walkthrough

Kahn’s algorithm

Edges A→B, A→C, B→D, peel indegree-0 nodes.

1 / 5

A
B
C
D
0123

Indegrees: A0 B1 C1 D1. Queue = [A], only nodes with no incoming edges.

q = deque([n for n in nodes if indeg[n]==0])

Live template

Line 1 active

1indeg = {u: 0 for u in nodes}
2for u, v in edges: graph[u].append(v); indeg[v] += 1
3q = deque(u for u in nodes if indeg[u] == 0)
4while q:
5 u = q.popleft(); order.append(u)
6 for v in graph[u]:
7 indeg[v] -= 1
8 if indeg[v] == 0: q.append(v)
9return order if len(order) == len(nodes) else []

Complexity: time O(V + E), space O(V + E)

O(V + E) time and space. Prefer Kahn when you also need cycle detection via leftover nodes. DFS topo is fine too; both beat repeated linear scans looking for free nodes.

Read the walkthrough as text

Course schedule order. Courses 0..3, edges (prereq → course): 0→1, 0→2, 1→3, 2→3.

  1. Indegrees: [0,1,1,2]. Queue starts with 0.
  2. Take 0; reduce 1 and 2 to 0; enqueue them.
  3. Take 1 and 2 (order among them may vary); each reduces 3.
  4. Take 3. Order length 4 → valid, e.g. [0,1,2,3].

If an edge 3→0 existed, someone would remain with indegree > 0.

3Recognise it

Kinds of problems (7)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Kahn's algorithm (BFS)

    Example. Topological order of course prerequisites.

    How. Zero in-degree queue; peel nodes, decrement neighbours; order length n means no cycle.

  • DFS post-order

    Example. Topo sort by finishing times.

    How. DFS post-order stack, reverse for order; cycle if back edge in directed DFS.

  • Cycle detection in dependencies

    Example. Can you finish all courses?

    How. Kahn: fewer than n processed ⇒ cycle; or three-colour DFS on prerequisite graph.

  • Alien dictionary

    Example. Derive character order from sorted alien words.

    How. Compare adjacent words for first mismatch edge; topo sort letters; empty if invalid prefix.

  • Longest path in a DAG

    Example. Critical path length in a DAG with weights.

    How. Topo order relax edges: dist[v] = max(dist[v], dist[u] + w).

  • Reachability between all pairs (transitive closure)

    Example. After topo on DAG, which nodes reach which?

    How. Process backward in topo: propagate reach bits or DP from each source.

  • Nodes with no incoming edges

    Example. Sources to start a dependency traversal.

    How. Nodes with in-degree 0 after building the graph, Kahn’s initial queue.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Edge direction reversed

    Why it happens. “A depends on B” reads as A → B in your head.

    How it fails. Edge course → prerequisite makes both appear last, order satisfies dependencies backward.

    Fix. Edge prerequisite → dependent (must finish prereq before course).

  • Cycle not detected

    Why it happens. Partial order from processed nodes still prints something.

    How it fails. Cycle A→B→A: Kahn processes 2 nodes, returns order length < n but code returns it anyway.

    Fix. Success iff len(order) == n (or all nodes coloured in DFS).

  • Nodes without edges

    Why it happens. Only nodes in edges get in-degree entries.

    How it fails. Isolated node never in-degree zero set, dropped from order despite no incoming edges.

    Fix. Initialize all nodes in indeg map before applying edges.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons