DFS applications — cycle detection (directed and undirected): Visual walkthrough

Before we start, one word we cannot skip: DFS (Depth-First Search). It means "keep walking forward into new rooms as far as you can; only when stuck do you back up." We lean on it heavily — if it is fuzzy, visit Depth-First Search first. Everything below is a drawing of one DFS in motion.

Step 1 — What a "path we are still inside" looks like

WHAT. Picture DFS as a person walking through rooms (nodes), unrolling a string behind them so they never forget the way back. At any instant, that string is a straight chain from the start room to the room they are standing in.

WHY. The whole idea of a cycle is "I got back to somewhere I've been." But where I've been splits into two very different kinds of place: places still connected to me by the string in front of me, versus places I already finished and packed the string up from. This step draws that string so we can point at it later.

PICTURE. The red chain is the string — the rooms currently "open," the ones whose exploration has not finished. In code this chain is literally the recursion stack.

Figure — DFS applications — cycle detection (directed and undirected)

Step 2 — Three colors name three moments in a room's life

WHAT. Give every room one of three colors as DFS proceeds:

White — never entered.
Gray — entered, string still attached (on the stack).
Black — entered and fully finished, string packed up.

WHY. We need a way, at the exact moment we look through a door, to ask: is the room on the other side part of my current string, or not? Colors are that answer, computable in $O (1)$ . Gray is the crucial one — it is the color of "still inside."

PICTURE. Same three rooms as Step 1, now colored. The single red room is the one we are actively in (top of stack); the other grays are its ancestors, black rooms are done.

Step 3 — The moment a directed cycle is born

WHAT. We are standing in room $C$ . We look through a one-way door and it leads to room $A$ . We check $A$ 's color — it is GRAY.

WHY. Gray means $A$ is still on my string (Step 2's equivalence). So the door $C \to A$ plus the existing string $A \to B \to C$ forms a closed loop I can walk forever. That closed loop is the cycle — and the door that closed it has a name.

PICTURE. The red arrow is the offending door $C \to A$ . Follow the black string forward, then jump the red arrow back — you return to where you started. That red arrow is a back edge.

Step 4 — Why reaching a BLACK room is not a cycle

WHAT. Different graph: $A \to B, A \to C, B \to C$ . DFS finishes $C$ (packs its string), turns it black, finishes $B$ , then back in $A$ opens the door $A \to C$ . $C$ is BLACK.

WHY. Black means $C$ 's string was already packed up — $C$ is not on my current string. So the door $A \to C$ does not close a live loop; it just re-enters a finished area from a second direction. In edge language this is a forward edge (or a cross edge). No cycle.

PICTURE. The red arrow $A \to C$ points at a black (finished) room. There is no string leading from $C$ back to $A$ , so no loop closes.

Step 5 — The undirected surprise: the edge you came in on

WHAT. Switch to undirected graphs, where an edge $u - v$ is a two-way door stored in both rooms' door lists. We walk $A \to B$ . Now standing in $B$ , we scan its doors and — of course — one door leads back to $A$ , which is already visited.

WHY. If we blindly used "visited neighbor = cycle," every single edge would trigger a false alarm, because you can always see the door you just walked through. That reverse door is not a second route; it is the same door. So we must remember which room we came from and skip it.

PICTURE. Black arrow = the door we walked ( $A \to B$ ). The red arrow is the reverse copy the door list hands back to us. It is a mirage — not a cycle.

Step 6 — The moment a real undirected cycle appears

WHAT. Triangle $A - B - C - A$ . Walk $A \to B \to C$ . Standing in $C$ , scan doors: $B$ is the parent (skip it), but $A$ is visited and is not the parent ( $C$ 's parent is $B$ ).

WHY. A visited, non-parent neighbor means there is a second, independent route back to $A$ : the string route $A \to B \to C$ and the direct door $C - A$ . Two routes between two rooms = a loop. This is the genuine article.

PICTURE. Black string $A \to B \to C$ ; the red door $C - A$ is a different edge from the one we arrived on, so it closes a real triangle.

Step 7 — Degenerate cases you must still handle

WHAT. Four edge cases the pictures above didn't cover — each drawn as a mini-panel.

WHY. The contract is "the reader never hits a scenario you didn't show." These are the exact inputs that quietly break a naïve implementation.

PICTURE. Left→right: (1) self-loop $u \to u$ / $u - u$ — a cycle by itself; the string reaches its own room. (2) 2-cycle directed $A \to B \to A$ — smallest directed cycle; the parent-trick would wrongly skip it (why the trick is illegal for directed graphs). (3) parallel edges undirected $u = v$ (two doors) — a real cycle, but v != parent alone misses it; you must track edge indices, not just the parent. (4) disconnected components — a cycle can hide in a piece DFS never reached, so you must restart DFS from every unvisited room.

The one-picture summary

Everything compresses to a single decision made at each door: look through it, read the color / parent, react.

Recall Feynman retelling — the whole walk in plain words

You wander a maze unrolling string. The string in front of you (not yet packed) is your gray chain; rooms you finished and packed up are black; unentered rooms are white.

One-way maze (directed): every time a door opens, glance at the room beyond. If your string is still lying there (gray), you just walked in a circle — that door is a back edge, that's your cycle. If the string there is already packed up (black), no loop — you merely re-entered a finished wing. That's why one color isn't enough: only gray means danger.

Normal maze (undirected): every door is two-way, so from each room you'll always spot the door you just came through — ignore your parent door. But if you reach a room you've already visited through a different door, there are two ways back to it: a loop. Watch out for trick rooms — a door to itself is already a loop, twin doors between two rooms fool the "not-parent" test unless you tag the door itself, and cycles can lurk in a wing you never entered, so start a fresh walk from every untouched room.

Mnemonic glue: Gray means stay (on the stack) → back edge → directed cycle. Pardon the parent, panic on anyone else → undirected cycle.

Recall Self-check

In a directed graph, which node color makes an edge a back edge? ::: GRAY (still on the recursion stack). Why doesn't an edge to a BLACK node signal a cycle? ::: Black means finished/packed up — not on the current string — so no live loop closes. Why must undirected DFS skip the parent? ::: Each undirected edge is stored both ways; the reverse copy of the arrival edge would be a false alarm. Smallest directed cycle vs smallest simple undirected cycle? ::: Directed: 2 nodes A→B→A (or a self-loop). Undirected simple: 3 nodes (triangle). How do you catch cycles hidden in a disconnected component? ::: Restart DFS from every still-unvisited vertex.

Connections

Depth-First Search — the walk this entire page animates.
Back Edges and Edge Classification — the back edge of Step 3 formalised alongside tree/forward/cross edges.
Topological Sort — possible exactly when Step 4's "no back edge" holds (a DAG).
Union-Find (DSU) — detect undirected cycles (Steps 5–6) without DFS at all.
Strongly Connected Components — the same gray/black finish-time machinery, pushed further.
Bipartite Checking — another DFS-coloring cousin.