Topological sort: every prerequisite first

Your socks and your shirt can go on in either order, but your socks must go on before your shoes. A build is the same: a library has to be compiled before any program that uses it. Draw each task as a node and each “must come first” as an arrow, and you have a directed graph.

A topological order lists the tasks so that every arrow points forward: each task comes after everything it depends on. Often many orders work. Sometimes none does: if two tasks each wait for the other, neither can go first. This lesson finds an order, or proves there isn't one, in time proportional to the size of the graph.

dependency edge

An edge u → v says u must come before v: v depends on u. A prerequisite points at the course it unlocks.

topological order

A list of every node in which each edge u → v has u earlier than v.

in-degree

The number of edges into a node: how many things it waits for. A node with in-degree 0 is ready.

cycle

A path of edges that comes back to where it started, such as A → B → C → A.

DAG

A directed acyclic graph: a directed graph with no cycle.

These are eight courses, from Prg (programming) and Mth (maths) to ML (machine learning). An edge points from a course to one that needs it: Mth → DS says take maths before data structures. The visualiser runs Kahn's algorithm, and the number beside each node is its in-degree, counting only the prerequisites not yet placed.

A node can be placed once everything with an edge into it is placed, and Kahn's algorithm keeps that as a count. It counts each node's in-degree and queues every node whose count is 0. Then, until the queue is empty, it takes the front node, appends it to the order, and lowers the count of every node it has an edge to. A count that reaches 0 means that node's last prerequisite has just been placed, so it joins the queue.

So every edge points forward, and the queue only decides which ready node goes next. Counting the in-degrees reads every edge once. After that, each node is queued and taken out once, and each edge is examined once, when the node it leaves is placed: O(V + E) with adjacency lists (O(V²) with a matrix), and O(V) extra memory for the counts and the queue.

Here A, B and C are all ready at the start. At each step, predict which node leaves the queue next, or whether the edge about to be followed makes its node ready. The queue is first in, first out, and ready means a count of 0.

D became ready only on its second edge, from B, and F only on its second, from E. Four times the queue held more than one node, and each time any of them could have gone next: this small graph has 16 valid orders, and C, B, E, A, D, F is one of them.

Here is Kahn's algorithm in code, on three courses: ml needs both maths and code. unlocks holds each course's outgoing edges, the courses that need it. indeg starts at 0 for every course, and each edge adds 1 to the course it points to. The queue is a list with a head index, as in breadth-first search; every course that leaves it joins the order, so the function returns the list itself. The second print compares the number placed with the number of courses.

def course_order(unlocks):
    indeg = {}
    for u in unlocks:
        indeg[u] = 0
    for u in unlocks:
        for v in unlocks[u]:
            indeg[v] += 1
    queue = []
    for u in unlocks:
        if indeg[u] == 0:
            queue.append(u)
    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        for v in unlocks[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return queue

courses = {'maths': ['ml'], 'code': ['ml'], 'ml': []}
plan = course_order(courses)
print(' '.join(plan))
print(str(len(plan)) + ' of ' + str(len(courses)))

The course ml joined the queue on its second edge, not its first: that wait is what separates Kahn's algorithm from breadth-first search.

The order code, maths, ml would be just as valid: the program put maths first only because the dictionary lists it first. That is a tie-break, like the visualiser's first in, first out, not the one right answer.

Kahn's algorithm has no separate step for cycles. It simply runs out of ready nodes.

So the test is a count: fewer than V nodes placed means a cycle. Each stuck node has an edge in from another stuck node, or its count would have reached 0, so stepping backwards along such edges must come back to a node already passed: that loop is a cycle. And no list can order a cycle, since whichever of its nodes comes first has an edge into it from one listed later. A topological order exists exactly when the graph is a DAG, and Kahn's algorithm finds one or proves there is none.

The second O(V + E) method uses depth-first search. Take any edge u → v as DFS looks at it from u. If v is undiscovered, DFS(v) runs and finishes before u does. If v has finished, it finished first. If v is still on the call stack, v reaches u, and the edge closes a cycle. So in a DAG, v always finishes before u: list the nodes as they finish, then reverse the list.

Here A reaches every node; in general, start a new DFS from each node not yet discovered, adding to the same list.

Wherever there are dependencies, there is a topological sort: builds, package installs, a spreadsheet recalculating each cell after the cells its formula reads, and backpropagation, which sends gradients back through a computation graph in reverse topological order.

• A topological order lists every node so each edge u → v has u first. One exists exactly when there is no directed cycle, and there are often many: ready nodes can go in any order.
• Kahn's algorithm counts in-degrees, queues the nodes with none, then repeatedly places one and lowers the counts of the nodes it points to. A node joins the queue when its last prerequisite is placed, not its first. O(V + E).
• Fewer than V nodes placed means a cycle: the rest are on it or stuck behind it.
• DFS works too: reverse the finishing order, not the discovery order. An edge to a node still on the call stack means a cycle.
• Next: strongly connected components, groups of nodes that can all reach each other; shrink each group to one node and what is left is a DAG. Practise with Can Every Course Be Taken? and Course Order, write the DFS way in Run backpropagation in the right order, or open the topological sort visualiser and try a graph of your own.