Overview

A topological order of a directed graph lists every vertex so that each edge u → v has u before v. Build systems compile libraries before the programs that use them, package managers install dependencies first, and universities sequence prerequisite courses — all are topological sorts. Such an order exists exactly when the graph has no directed cycle (it is a DAG).

Kahn's algorithm is the most practical way to compute one: repeatedly take a vertex with no remaining incoming edges, output it, and remove its outgoing edges. If you run out of such vertices before outputting everything, the remaining vertices form a cycle — which is how "can all courses be finished?" is answered.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Kahn's algorithmO(V + E)
DFS-based sortO(V + E)

Patterns to recognise

Can it be done? / In what order?

Use it for: Course schedule I and II, build order.

Run Kahn's; success means the output contains every vertex.

Three-colour DFS

Use it for: Find eventual safe states, cycle detection.

White = unvisited, grey = on the stack, black = finished.

Longest path in a DAG

Use it for: Parallel courses III, longest increasing path in a matrix.

Relax edges in topological order, tracking the best value per vertex.

Code template

Course Schedule II — Kahn's algorithm
from collections import deque


def find_order(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for course, pre in prerequisites:
        graph[pre].append(course)            # pre must come before course
        indegree[course] += 1
    queue = deque(i for i in range(num_courses) if indegree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == num_courses else []   # [] means a cycle

Common mistakes

  • Getting the edge direction backwards — write down "u must come before v" and draw u → v.
  • Topological sort only applies to directed graphs.
  • Vertices with no edges at all still belong in the order; seed the queue from every vertex.

Quick check

Three questions on Topo Sort. Get all three right to earn +15 XP.

  1. A topological order exists only when the graph is:

  2. Kahn's algorithm begins with which vertices?

  3. How does Kahn's algorithm reveal a cycle?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Topo Sort?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor