How Do Directed Cycles and Topological Order Work?
Enrichment: a directed acyclic graph has a topological order in which every edge points forward. Kahn's algorithm removes zero-indegree vertices; leftovers prove a directed cycle.
Enrichment: beyond the current exercises
A directed edge u → v permits travel from u to v, not automatically back again. Direction models prerequisites, build dependencies, and data pipelines. A directed acyclic graph (DAG) contains no directed cycle. Every DAG has at least one topological order: a sequence in which each edge's source appears before its destination. The current graph exercises use undirected edges and do not require topological sorting; this article extends the same adjacency-list and traversal ideas.
Both A, B, C, D and A, C, B, D are valid. A topological order is usually not unique. Adding D → A creates a directed cycle, and no linear order can put every source before its destination.
Kahn's algorithm
The indegree of a vertex is the number of directed edges entering it. A zero-indegree vertex has no unmet prerequisite, so it may appear next. Kahn's algorithm places every current zero-indegree vertex in a queue, removes one, and decreases the indegree of each outgoing neighbour. A neighbour joins the queue exactly when its last prerequisite is removed.
Press Run to execute this example. Use console.log to print a value.
Expected output:
[ 'A', 'B', 'C', 'D' ]
null
The exact first order depends on how zero-indegree vertices are queued. Returning null is unambiguous here: it means no topological order exists, not that the graph has no vertices. An empty graph validly returns an empty order.
The integer endpoints index the labels, outgoing, and indegree arrays, so the snippet validates both endpoints while building. The queue uses a moving front index to avoid the repeated shifting cost of Array.shift(). Parallel edges are allowed by the code: each copy increments indegree once and is later decremented once. A self-loop increments its own vertex's indegree and correctly prevents a complete order.
Why the cycle test works
The loop invariant is: indegree[v] counts incoming edges from vertices not yet output. Removing a vertex deletes exactly its outgoing edges from that remaining graph. Therefore a queued vertex really has no remaining prerequisite.
Every non-empty DAG has a zero-indegree vertex. If every vertex had an incoming edge, repeatedly following incoming edges in a finite graph would eventually revisit a vertex and form a directed cycle. Consequently, if the queue empties while vertices remain, those remaining vertices contain a cycle. Conversely, a cycle never supplies its own first zero-indegree vertex because each cycle vertex still has an incoming cycle edge.
DFS alternative
Depth-first search can also find a topological order. Give each vertex three states: unvisited, active on the current recursion path, and finished. An edge to an active vertex is a back edge and proves a directed cycle. Append a vertex only when it finishes, then reverse the finish sequence.
Do not use only a boolean visited mark for directed cycle detection. An edge to a finished vertex is harmless, while an edge to an active ancestor is a cycle; one boolean cannot distinguish them. In an undirected graph, the immediate parent edge must instead be ignored, because every stored edge appears in both directions.
Complexity and invariants
Building adjacency lists and indegrees takes O(V + E) time and space. Each vertex enters the queue once, and each directed edge causes one decrement, so the algorithm remains O(V + E). The queue, indegree array, output, and adjacency lists together use O(V + E) memory.
| Question | Correct result |
|---|---|
| Is there any legal prerequisite order? | output length equals V |
| Which order is the only valid one? | not generally defined |
| Does a self-loop form a cycle? | yes |
| Do parallel edges break the algorithm? | no, if both are counted and decremented |
| Is an empty graph acyclic? | yes |
The central invariant is not “all prerequisites are globally complete.” It is “the next queued vertex has no incoming edge from the remaining graph.” Vertices already output are deliberately absent from that remaining graph.
Common pitfalls
Storing only indegrees without outgoing neighbours leaves no efficient way to perform decrements. Decrementing on discovery rather than removal can make a prerequisite disappear too early. Starting from one zero-indegree vertex misses disconnected DAG components; seed the queue with all of them. Returning the partial output when a cycle remains presents an invalid schedule as a complete answer.
Topological sorting answers precedence, not shortest path. Multiple valid orders are expected, so tests should verify that every vertex appears once and every edge points forward rather than demanding one arbitrary sequence—unless the problem specifies a tie-breaker. A min-heap can impose the lexicographically smallest available label when such a tie-breaker is required.
Disconnected directed graphs are not a special case. Seeding every zero-indegree vertex lets Kahn's algorithm process all acyclic components. An isolated vertex has indegree 0 and belongs in every complete result exactly once, even though no edge mentions it.