A topological sort is a linear ordering of the vertices of a directed acyclic graph such that for every directed edge u to v, u comes before v in the ordering. It is the order in which you can carry out tasks when some tasks must finish before others can start. A graph can have many valid topological orders or, if it contains a cycle, none at all.

Kahn's algorithm first computes the indegree of every vertex, then puts all zero-indegree vertices in a queue. It repeatedly removes a vertex from the queue, appends it to the output order, and decrements the indegree of each of its successors. Any successor whose indegree drops to zero is added to the queue, and the process repeats until the queue is empty.

The indegree of a node is the number of edges pointing into it, that is the count of its direct predecessors. A node with indegree zero has no remaining dependencies and is therefore ready to be placed next in the order. Kahn's algorithm is driven entirely by tracking how indegrees fall to zero as nodes are removed.

A cycle means a group of vertices each depend, directly or indirectly, on one another, so no member of the cycle can ever be first. With a cycle present, every vertex in it keeps a positive indegree forever and never enters the queue. That is why a topological order only exists for a directed acyclic graph (DAG).

It uses a property of Kahn's algorithm: if the algorithm finishes and the number of vertices placed in the order is less than the total number of vertices, the remaining vertices must lie on a cycle. The simulation lets you add a back edge that creates a cycle, then reports that no topological order exists because the count came up short.

No. Whenever two or more vertices have indegree zero at the same time, you may choose either one next, and each choice can lead to a different valid order. The number of distinct topological orders depends on the structure of the graph, and a fully chained graph has exactly one while a graph with no edges has every permutation.

Kahn's algorithm runs in O(V + E) time, where V is the number of vertices and E the number of edges. Each vertex is enqueued and dequeued once, and each edge is examined once when its source is removed. This linear performance is why topological sort scales well to very large dependency graphs.

Build tools like Make, Bazel, and package managers model files or packages as nodes and their dependencies as edges, then topologically sort that graph to decide a safe compile or install order. Building a target only after all of its dependencies are built is exactly the guarantee a topological order provides. If the dependency graph contains a cycle, the build tool reports it as an error rather than looping forever.

Course scheduling with prerequisites, spreadsheet cell recalculation, task and project scheduling, instruction scheduling in compilers, and resolving symbol dependencies in linkers all rely on topological order. Any setting where some items must precede others is a candidate. It is also a first step in algorithms that find the longest or shortest path in a DAG.

Kahn's algorithm is iterative and works forward by repeatedly removing zero-indegree vertices using a queue. The depth-first search approach instead recurses to the deepest descendants first and prepends each finished vertex to the order, producing the reverse of the finish-time order. Both run in O(V + E) time and both can detect cycles, but Kahn's makes the notion of dependencies ready to process more explicit.