Topological Sort & Cycle Detection

Some graphs represent dependencies rather than distances, course prerequisites, build steps, task pipelines, where a directed edge from u to v means "u must happen before v." A topological sort produces a linear ordering of all nodes that respects every one of those directed edges: for every edge u -> v, u appears somewhere before v in the output.

You cannot put your shoes on before your socks, or your jacket on before your shirt. But you can put your watch on at any point. Writing those rules as arrows, socks to shoes and shirt to jacket, gives a dependency graph, and any sensible order to get dressed in is a topological order. Many different orders are fine, and if someone wrote the rules shoes before socks and socks before shoes, no order could ever work.

• -Each arrow u to v is a rule: u must come before v.
• -A valid way of getting dressed is a topological order: every rule is respected.
• -Rules that contradict each other in a loop are a cycle, and then no valid order exists.

Kahn's algorithm builds that ordering by repeatedly picking off nodes with no unmet prerequisites. First, compute every node's in-degree, the number of edges pointing into it, i.e. how many other nodes must come before it. Any node with in-degree 0 has no prerequisites left, so it is safe to place next in the output immediately. Once a node is placed, every edge leaving it is effectively "used up." Decrement the in-degree of each of its neighbors, and if any neighbor's in-degree drops to 0 as a result, that neighbor just became ready too, and joins the queue.

Take A before B, A before C, B before D and C before D. The in-degrees (how many arrows point in) are A: 0, B: 1, C: 1, D: 2. The queue starts with A, the only node with in-degree 0.

• -Dequeue A and append it to the order. Decrement B to 0 and C to 0, so both join the queue.
• -Dequeue B. Decrement D from 2 to 1. D is not ready yet, because it still waits on C.
• -Dequeue C. Decrement D from 1 to 0, so D joins the queue.
• -Dequeue D. The order is A, B, C, D, which has all 4 nodes.

A, C, B, D would have been just as valid. A topological order is almost never unique, and any order that respects every arrow is a correct answer.

Every node that is added to the queue eventually reaches the order. If the graph is a true DAG (directed acyclic graph), each node's in-degree is eventually whittled down to 0, so the order ends up as long as the graph.

A cycle breaks that. In A to B to C to A, every node waits for another node inside the same loop, so none ever reaches in-degree 0. None is queued and none is appended to the order.

So a mismatch between len(order) and len(graph) is a direct, reliable sign that a cycle exists and that no valid order is possible. For that three-node loop the queue starts empty, the order stays empty (length 0, not 3), and the function returns None.

What it does not do is name the cycle. The nodes left with a non-zero in-degree are either inside a cycle or depend on one. To report the actual cycle, follow edges among those nodes until a node repeats.

• -Kahn's algorithm: compute in-degrees, seed the queue with in-degree-0 nodes, repeatedly dequeue a node, append it to the order, and decrement its neighbors' in-degrees.
• -A node joins the queue exactly once its in-degree hits 0, meaning every prerequisite it has has already been placed in the output.
• -If the final order is shorter than the graph, some nodes never reached in-degree 0, which only happens when they are part of (or depend only on) a cycle.
• -Real-world uses: build systems ordering compilation steps, package managers resolving dependencies, and course-scheduling systems checking prerequisites are satisfiable.