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.

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.

Every node that gets added to the queue eventually reaches order - the queue only runs dry once every node with a path to reaching in-degree 0 has been processed. If the graph is a genuine DAG (directed acyclic graph), every node eventually gets its in-degree whittled down to 0 and processed, so order ends up the same length as the graph. But if a cycle exists - say A -> B -> C -> A - every node in that cycle permanently depends on another node inside the same cycle: none of them can ever reach in-degree 0, because whichever one you look at is still waiting on a predecessor that is itself waiting on someone inside the same loop. Those nodes are never queued and never appended to order, so a mismatch between len(order) and len(graph) is a direct, reliable signal that a cycle exists and no valid ordering is possible.

• -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.