Detecting Cycles

The 10-second versionCopy Anchor Link

A cycle is a path that comes back to where it started. Detecting one is the single most common graph question, and the answer depends on whether your edges are lines (undirected) or arrows (directed). In an undirected graph, a cycle exists the moment DFS finds an edge to a vertex it has already visited that isn't the parent you came from. In a directed graph you need three colours — white, gray, black — because an edge to a gray (still-on-the-path) vertex is a cycle, while an edge to a black one is harmless. And on a plain linked list, two pointers moving at different speeds spot a loop using no extra memory at all.

Why this existedCopy Anchor Link

Nobody set out to "detect cycles." They kept getting bitten by them.

An operating system with several deadlocked processes, each waiting on a resource another one holds, forms a cycle in the "who waits for whom" graph — and the OS has to notice or it's stuck forever. A build system whose files depend on each other in a big loop can never finish. A spreadsheet where A1 depends on B1 which depends on A1 is a circular reference. Cycles are the shape of "this can never complete," so detecting them is detecting the impossibility before you pay for it.

The tools arrived piecemeal:

• 1962 — Arthur B. Kahn publishes his topological-sort algorithm, and a cycle falls out as a by-product: if you can't finish ordering the vertices, whatever's left over is the cycle.
• 1964 — Bernard Galler and Michael Fischer build the union-find structure and show it catches undirected cycles as you add edges.
• 1967 — Robert Floyd describes the tortoise-and-hare pointer trick, a way to find a loop in a sequence with constant memory.
• 1972 — Robert Tarjan formalises the white/gray/black DFS that pinpoints a back edge in linear time.

Why it mattered then: each method answers a slightly different question under different constraints — directed or not, cheap memory or not — so modern software uses all four, depending on the shape of the graph in front of it.

Inside the inventor's headCopy Anchor Link

Start with the version everyone writes first, because it seems obviously right: walk the graph, and if you ever step onto a vertex you've already visited, cry "cycle!" Watch it betray you.

Take a directed graph shaped like a diamond: 0 → 1 → 3 and 0 → 2 → 3. Walking 0 → 1 → 3, then coming back to explore 0 → 2, you arrive at 3 again. A naive visited-set screams "cycle!" — but there's no cycle. 3 is just reachable two ways. You've confused "I've been here before" with "I'm standing on my own ancestor."

That's the pivot. What you actually need to know is whether the vertex you're stepping onto is still on your current path — an ancestor you haven't finished with yet — versus one you've already fully explored and moved past. One bit of "visited" can't tell those apart. So you give each vertex a colour:

• white — never seen.
• gray — discovered, still being explored, sitting on the current path.
• black — completely finished.

Now "an edge into a gray vertex" means precisely "I looped back onto my own ancestor" — a cycle. "An edge into a black vertex" is just a shortcut you've already mapped.

Floyd found a totally different escape hatch for the special case where the graph is a single chain with a loop — a linked list. What if you can't afford even a visited set? Send two walkers down the list at once: a tortoise that moves one node per step and a hare that moves two. If there's no loop, the hare simply runs off the end. If there is a loop, the hare laps the tortoise and they must eventually land on the same node — and racing two points against each other is O(1) memory because neither is storing anything.

The hare enters the loop first and keeps gaining a step on the tortoise every round; inside a loop of length L they collide within L steps. That's the whole proof, and it needs no memory.

The final approachCopy Anchor Link

The algorithm, as a flowCopy Anchor Link

For a directed graph, walk every unvisited start with the three colours — the gray edge is the tell:

The invariants that make it correctCopy Anchor Link

1. Gray = on the current recursion path. The set of gray vertices is exactly the path from the DFS root down to the vertex being explored. An edge into gray is, by definition, a way back to an ancestor — a cycle.
2. An edge into black is safe. A black vertex finished earlier; it cannot lead back to anything still on the path, or it wouldn't have finished first.
3. In the undirected case, ignore the edge you arrived by. The vertex you came from is always "visited," but that single edge is the tree edge, not a cycle. You must compare against the parent — a visited neighbour that isn't your parent is the cycle.
4. Kahn's leftover test is the same truth, counted. If you repeatedly remove vertices with indegree zero and run out of things to remove while vertices remain, those remainders can only be vertices locked in a cycle. No cycle means the removal empties the graph.

A worked traceCopy Anchor Link

A directed graph with a loop: 0 → 1, 1 → 2, 2 → 0, and 2 → 3 hanging off the side.

• dfs(0) — colour 0 gray, scan its only neighbour 1.
• dfs(1) — colour 1 gray, scan its only neighbour 2.
• dfs(2) — colour 2 gray, scan its neighbours 0 and 3.
• First neighbour is 0 — and 0 is gray. Back edge! Cycle found, and we can stop immediately. (Neighbour 3 never even gets visited.)

Contrast that with the diamond 0 → 1 → 3, 0 → 2 → 3. When we finally reach 3 the second time, we'd earlier have coloured 3 black — so the edge 2 → 3 hits a black vertex and is correctly ignored. Colors, not a single bit, are what keep the diamond out of the false-positive pile.

It in codeCopy Anchor Link

Three-colour DFS for directed graphs:

// color: 0 = white (unseen), 1 = gray (on the current path), 2 = black (done)function hasCycle(u, adj, color) {  color[u] = 1;                                 // gray  for (const w of adj[u]) {    if (color[w] === 1) return true;            // edge into gray → back edge → cycle    if (color[w] === 0 && hasCycle(w, adj, color)) return true;  }  color[u] = 2;                                 // black  return false;}function graphHasCycle(adj) {  const color = new Array(adj.length).fill(0);  for (let i = 0; i < adj.length; i++)    if (color[i] === 0 && hasCycle(i, adj, color)) return true;  // every component  return false;}

For undirected graphs a single visited set plus the parent is enough — no colors needed, because an undirected "back edge" can only ever point at your parent or a genuine ancestor:

// An edge to a visited vertex that is NOT the parent we came from is a cycle.function hasCycleUndirected(u, parent, adj, seen) {  seen[u] = true;  for (const w of adj[u]) {    if (!seen[w]) {      if (hasCycleUndirected(w, u, adj, seen)) return true;    } else if (w !== parent) {      return true;                                // visited, and not the way we came    }  }  return false;}

There's a second, arguably prettier way to do the undirected case: build up the graph edge by edge with union-find (which we'll meet much later, when we do Kruskal's algorithm). Two vertices already being in the same cluster means the new edge closes a loop. Same answer, delivered as the edges arrive instead of after the fact.

Cost tableCopy Anchor Link

The three graph methods all run in linear time; the differences are in what they give you back. Three-colour DFS stops at the first back edge; Kahn's finishes the whole ordering and hands you the leftovers; Floyd needs no memory because it only ever visits a single chain.

Where you meet it todayCopy Anchor Link

• Circular dependencies. A package manager refusing to install because A needs B needs A is three-colour DFS (or Kahn's) on the dependency graph.
• Deadlock detection. The OS builds a "process → resource it waits for" graph and looks for a cycle; a cycle means nobody can proceed.
• Loop detection in streams. hasCycle on a linked list is Floyd's trick, and it generalises to detecting repeating state in any function that maps inputs to outputs.
• Spreadsheets and config validation. "Circular reference detected" is the same check, dressed up for a human.

Here's Floyd's algorithm as you'd actually write it — note the complete absence of any visited set:

// true if the list has a loop. O(n) time, O(1) space — no extra storage at all.function hasCycle(head) {  let slow = head, fast = head;  while (fast && fast.next) {    slow = slow.next;               // tortoise: one step    fast = fast.next.next;          // hare: two steps    if (slow === fast) return true; // they met → there is a loop  }  return false;                     // hare fell off the end → no loop}

RecapCopy Anchor Link

• A cycle is a path back to its own start; detecting one is detecting "this can never finish."
• Undirected: DFS plus a remembered parent — an edge to a visited, non-parent vertex is a cycle. (Union-find finds the same thing as edges arrive.)
• Directed: use three colours. An edge into a gray vertex is a back edge — a cycle.
• Kahn's algorithm tells you indirectly: if you remove the zero-indegree vertices and some are left over, those leftovers are stuck in a cycle.
• Floyd's tortoise-and-hare finds a loop in a chain with two pointers and O(1) memory.

Next up: Topological Sort — turning a loop-free directed graph into a list you can actually execute in order.