Topological sort

Problem

The input is a set of items and a set of rules of the form "a must come before b". You are asked for any valid order, for whether one exists, for the earliest round in which each item can happen, or for something that can be derived from the order, such as a hidden alphabet. Sometimes the rules are not given but must be read from the data first.

Intuition

Getting dressed has an order: socks before shoes, trousers before belt. You do not need to plan it all at once. At any moment, pick something that has no unmet requirement, do it, and cross it off every other item's list of requirements. If you can always find such an item, you finish with a valid order. If at some point everything left still has an unmet requirement, you have found a circle (shoes need socks need shoes) and no order exists.

Kahn's algorithm is exactly that. It counts for each node how many prerequisites are unfinished (its in-degree), starts with the nodes that have none, and each time it finishes a node it reduces the count of every node that depended on it. The depth-first version reaches the same set of answers from the other side: the node that finishes last in a depth-first search has nothing after it that is unfinished, so listing nodes in reverse finishing order puts every node before everything it points to.

The small blue dot marks the arrow's head. Every dependency goes from a column on the left to a column on the right, which is what a topological order means. Nodes in one column are independent of each other and could happen in parallel. The diagram scrolls sideways on a narrow screen.

Mechanics

Kahn's algorithm

Compute the in-degree of every node. Put the zero in-degree nodes in a queue. Repeatedly remove a node, append it to the answer, and decrement the in-degree of each node it points to; a node whose count reaches zero joins the queue. Finish when the queue is empty. If the answer has fewer nodes than the graph, the rest are blocked by a cycle.

Why it is correct. A node is queued only when every prerequisite has already been appended, so each edge goes forward in the answer. If the answer is short, every node left over still has an unfinished prerequisite that is itself left over; following those prerequisites backwards can never end, so it must revisit a node, which is a cycle. Conversely a cycle's nodes never reach in-degree zero, so they are always left over.

The depth-first version

Run a DFS with three states (unseen, on the path, finished) and append a node to a list the moment it finishes. An edge into an on-path node is a cycle. Otherwise the reversed list is a topological order, because when a node finishes, everything it points to has already finished and sits earlier in the list.

Rounds and longest chains

Process the queue one layer at a time and count layers. A node lands in round k + 1 where k is the longest chain of prerequisites below it, so the number of rounds is the "minimum semesters" answer when any number of items may proceed together. The same counting yields the longest path in a DAG, a task no ordinary graph can do in linear time.

Deriving the edges

Sometimes the graph is hidden. In a list of words sorted by an unknown alphabet, compare each word with the next: the first position where they differ gives one rule, "this letter comes before that one". Later positions say nothing. If the longer word comes first while the shorter is its prefix, the list cannot be sorted under any alphabet.

With the extra edge, only node 4 has in-degree zero. After it is removed, the others are all still waiting on someone who is waiting on them. Node 0 is not on the cycle but is stuck behind it.

Worked example

Six items with rules 5→2, 5→0, 4→0, 4→1, 2→3, 3→1. The in-degrees are 0: 2, 1: 2, 2: 1, 3: 1, 4: 0, 5: 0.

The two orders differ and both are correct: a DAG usually has many topological orders, and a problem that wants one specific order must say how to break ties. The number of rounds, 4, is the longest chain 5→2→3→1 counted in nodes.

A hidden alphabet. From the sorted words wrt, wrf, er, ett, rftt, comparing neighbors yields the rules t<f, w<e, r<t, e<r, and sorting them gives the alphabet wertf. The list ["abc", "ab"] is impossible (the helper reports a prefix problem: a word is sorted before its own prefix), and ["z", "x", "z"] demands both z<x and x<z, so the helper reports a cycle and no order.

Peeling leaves. For the tree with edges 3-0, 3-1, 3-2, 3-4, 5-4, removing all leaves takes 1 round and leaves nodes 3 and 4, the roots that give the shortest rooted tree.

Implementation

from collections import defaultdict, deque


def topological_order(n, prerequisites):
    adj = defaultdict(list)
    indegree = [0] * n
    for course, before in prerequisites:
        adj[before].append(course)
        indegree[course] += 1
    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in adj[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == n else []


def can_finish(n, prerequisites):
    return len(topological_order(n, prerequisites)) == n

Variations and edge cases

def alien_order(words):
    letters = {ch for word in words for ch in word}
    adj = {ch: set() for ch in letters}
    indegree = {ch: 0 for ch in letters}
    for first, second in zip(words, words[1:]):
        for a, b in zip(first, second):
            if a != b:
                if b not in adj[a]:
                    adj[a].add(b)
                    indegree[b] += 1
                break
        else:
            if len(first) > len(second):
                return ""
    queue = deque(ch for ch in letters if indegree[ch] == 0)
    out = []
    while queue:
        ch = queue.popleft()
        out.append(ch)
        for nxt in adj[ch]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return "".join(out) if len(out) == len(letters) else ""


def minimum_height_trees(n, edges):
    if n == 1:
        return [0]
    adj = [set() for _ in range(n)]
    for a, b in edges:
        adj[a].add(b)
        adj[b].add(a)
    leaves = [i for i in range(n) if len(adj[i]) == 1]
    while n > 2:
        n -= len(leaves)
        following = []
        for leaf in leaves:
            neighbor = adj[leaf].pop()
            adj[neighbor].discard(leaf)
            if len(adj[neighbor]) == 1:
                following.append(neighbor)
        leaves = following
    return leaves


def longest_chain(n, edges):
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for a, b in edges:
        adj[a].append(b)
        indegree[b] += 1
    layer = [i for i in range(n) if indegree[i] == 0]
    depth = 0
    while layer:
        depth += 1
        following = []
        for node in layer:
            for nxt in adj[node]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    following.append(nxt)
        layer = following
    return depth

• Edge direction. "Course a requires b" is the edge b→a. Reversing it silently produces a valid but reversed order. Say the direction aloud before coding.
• Duplicate edges. Counting a repeated edge twice in the in-degree but visiting it once (or the reverse) leaves a node stuck. Deduplicate with a set, or be consistent on both sides.
• Letters that appear in no rule. In the alien alphabet they must still be in the answer; seed the node set from all letters, not only from edges.
• Prefix trap. ["abc", "ab"] is invalid even though no letters differ. Check lengths when the comparison loop finds no difference.
• Several valid orders. If the judge needs a specific one (lexicographically smallest), use a heap in place of the queue.
• Edge cases: no edges (any order, all nodes), a self-loop (always a cycle), a disconnected graph (Kahn handles it, since all zero in-degree nodes start), and a single node.

Complexity and tradeoffs

• Time: O(V + E). Each node is queued once and each edge decrements one counter once.
• Space: O(V + E) for the adjacency list, plus O(V) for in-degrees and the queue.
• Baseline. Repeatedly scanning for a node with no unfinished prerequisite costs O(V · (V + E)). Keeping a count and a queue is what makes it linear.
• Kahn or DFS. Kahn is iterative, naturally layered, and detects a cycle by counting. DFS needs recursion (or an explicit stack) but reports the cycle itself and fits problems that already traverse recursively.
• When it fails. It needs directed edges and no cycle; for "are these connected" with undirected links use union-find. Rules with costs or deadlines on top of the order (critical path with durations) extend the layering into a longest-path dynamic program over the order.

Problems

Course Schedule asks only whether an order exists; Course Schedule II asks for one. Alien Dictionary hides the graph inside adjacent words. Minimum Height Trees uses the same peel-the-boundary idea on an undirected tree. Course Schedule IV and Build a Matrix With Conditions use the order as a stepping stone: reachability between courses, and positions in two independent orders for rows and columns.

Medium

• 207. Course Schedule Blind 75 Grind 169 NeetCode 150 NeetCode 250
  All courses can be taken exactly when the prerequisite graph has no cycle, which Kahn's algorithm checks by trying to remove every node.
• 210. Course Schedule II Grind 169 NeetCode 150 NeetCode 250
  Kahn's algorithm's removal order is a valid course order, and returning fewer than n courses means there is a cycle.
• 310. Minimum Height Trees Grind 169 NeetCode 250
  Repeatedly trim the current leaves; the one or two nodes left at the end are the centres of the tree.
• 1462. Course Schedule IV NeetCode 250
  Propagate each course's set of prerequisites along a topological order, so every query becomes a set lookup.

Hard

• 269. Alien Dictionary Blind 75 Grind 169 NeetCode 150 NeetCode 250
  The first differing letter of each adjacent word pair gives an ordering edge, then a topological sort finds the alphabet or a cycle.
• 2392. Build a Matrix With Conditions NeetCode 250
  The row and column conditions are independent, so two topological sorts give each number's row and column.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 329. Longest Increasing Path in a Matrix Hard

Connections

Topological sort is graph traversal with a count of unmet dependencies. The order it produces is what makes dynamic programming on a DAG possible (solve each node after everything it depends on), and the same "remove the nodes with nothing blocking them" loop returns in shortest-path algorithms.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 20.4 (topological sort, with the proof via finishing times).
• Kahn, "Topological sorting of large networks", Communications of the ACM 5(11), 1962, the queue-and-in-degree algorithm.
• Sedgewick and Wayne, Algorithms, section 4.2 (directed graphs, DAGs and topological order).
• Skiena, The Algorithm Design Manual, section 7.10 (topological sorting and its applications).
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.