Graphs 0/61

Topological sort: ordering directed graphs · 3 of 3

Cycle detection

See why a directed cycle rules out every order, find and print one with a DFS that tracks unseen, active and finished vertices, and get a topological order from the same search.

2,122 words · 10 min read

Part 1 of 6 Cycles and DAGs

Directed cycles

Kahn's algorithm, the topological sort that keeps taking a vertex with no edges left into it, comes to a stop when some vertices wait for each other in a circle. A depth-first search can find out whether a directed graph has a cycle, and print the cycle when it has one.

A directed cycle is a path that follows edges in their direction and returns to the vertex where it began. In the graph with the edges 0→10 \to 1, 1→21 \to 2, 2→32 \to 3, 3→13 \to 1 and 3→43 \to 4, the path 1→2→3→11 \to 2 \to 3 \to 1 is a directed cycle. A graph with a directed cycle has no topological order. Whichever vertex of the cycle comes first in a list, the cycle has an edge into it from a vertex that comes later.

A directed graph without a directed cycle is called a directed acyclic graph, or DAG. Cycles are the only thing that can prevent a topological order: every DAG has one, and Kahn's algorithm finds it.

To see why, suppose the algorithm has stopped and some vertices are left. Each of them still has a count above 0, so each has an edge into it from another vertex that is left. Start at any of them and keep stepping backwards along such an edge. The graph is finite, so this walk must come to a vertex it has already visited, and the part of the walk between the two visits is a directed cycle. In a DAG, then, no vertex can be left.

The vertices Kahn's algorithm cannot take

The figure shows Kahn's algorithm on the five-vertex graph at the moment it stops:

Vertex 0 has been taken. Each of the other four vertices has a count of 1, so the queue is empty.

Four vertices are left, which tells us that the graph has a cycle. It does not tell us where the cycle is. Vertex 4 is left over too, although it is not on the cycle: it waits for vertex 3, which is. To find the cycle itself we use DFS.