3.5.6 · D5Graphs
Question bank — DFS applications — cycle detection (directed and undirected)
Before we start, one shared vocabulary reminder so nothing below uses an unearned word:
True or false — justify
A directed 2-cycle counts as a real cycle.
True. When DFS enters (Gray), goes to (Gray), then 's edge points back to which is still Gray — a back edge — so it is a genuine cycle, the smallest one possible in a directed graph.
In an undirected graph, reaching any already-visited node means a cycle.
False. Reaching the immediate parent is not a cycle — that's just the reverse copy of the edge you just walked. Only reaching some other visited node (a second route) is a real cycle.
A self-loop (an edge from a node to itself) is a cycle.
True. It is the shortest cycle of all: a one-edge path that returns to its start. In color terms, is Gray and its own edge points to a Gray node.
Reaching a Black node in a directed graph always means there is no cycle.
True for that edge. Black means the node's DFS already finished on another branch, so the edge is a forward/cross edge, not a loop onto the live stack. (Other edges elsewhere might still form a cycle.)
The parent-exception trick works fine on directed graphs if you're careful.
False. Directed edges are one-way, so there is no spurious reverse copy to forgive — and the trick would wrongly skip a true 2-cycle . Directed graphs need the Gray-check instead.
A connected undirected graph with nodes and exactly edges must be acyclic.
True. That edge count is precisely a tree, and a tree has no cycles; adding even one more edge would create exactly one cycle.
If DFS from one starting vertex finds no cycle, the whole graph is acyclic.
False. A cycle may hide in a disconnected component you never entered. You must loop over all vertices and start a fresh DFS from each unvisited one.
A directed acyclic graph (DAG) can always be topologically sorted, and vice versa.
True. "No back edge to a Gray node" is exactly the condition for both — see Topological Sort; the same DFS that finds no cycle produces a valid ordering.
Union-Find can detect cycles in a directed graph just as it does undirected.
False. Union-Find (DSU) merges undirected connectivity; it can't tell edge direction, so it can't distinguish a directed back edge from a harmless merge. Use 3-color DFS for directed graphs.
Every graph that has a back edge (in Back Edges and Edge Classification terms) has a cycle.
True. A back edge points to an ancestor still on the stack, and the tree-path down to the current node plus that back edge closes a loop — that is a cycle by definition.
Spot the error
Someone codes undirected detection but writes elif visited[v]: return True (no parent check). What breaks?
It fires on the very first edge of every DFS: after , node sees (visited) and screams "cycle." The reverse copy of the edge you came from is misread as a second route. Fix:
elif v != parent.A student uses colors WHITE/GRAY/BLACK on an undirected graph and flags a cycle the moment any neighbor is GRAY, with no parent check. Why wrong?
The parent is Gray too (you're still inside its call), so the edge back to it trips the check on every single edge. Undirected detection must forgive the immediate parent, not just look at color.
Code checks if color[v] == GRAY but places it after the if color[v] == WHITE and dfs(v) line. Any harm?
Logically the Gray branch still returns
True, but ordering the White-recursion first is fine here because a Gray neighbor is never White — the two conditions are mutually exclusive. No bug, just less readable. The real bug would be omitting the Gray check.In directed detection, a coder marks a node BLACK before the loop over its neighbors instead of after. What fails?
A back edge to that node would now see it as Black instead of Gray, so the cycle is missed. Black must mean "finished," which only happens after all descendants are explored — so it must be set after the loop.
To detect self-loops, a student relies only on v != parent in undirected DFS. Does it catch ?
Not reliably — a self-loop's neighbor is itself, and depending on whether is "parent" of itself, the check can silently pass. Self-loops need an explicit test:
if v == u (or edge-index tracking) marks a cycle immediately.An undirected graph has two parallel edges between and . The code uses v != parent and reports "no cycle." Correct?
No — two parallel edges are a cycle ( by different edges). The
v != parent test forgives the reverse of the first edge and mistakenly also forgives the second. Fix: track visited edge indices, not just the parent vertex.Someone claims "no White nodes left after one DFS ⇒ graph is connected." True?
Only if that DFS started from a vertex whose component is the whole graph. In a disconnected graph, the outer loop launches multiple DFS calls; all-visited at the end says nothing about connectivity, only about full coverage.
Why questions
Why does the directed algorithm need three colors, but the undirected one needs only visited/not-visited plus a parent?
Directed cycles depend on whether an ancestor is still live on the stack (Gray) versus already finished (Black) — two "visited" states that mean opposite things. Undirected graphs can't produce those harmless cross/forward edges the way directed ones can, so a single visited flag plus the parent suffices.
Why is a Gray neighbor a cycle but a Black neighbor is not, in directed graphs?
Gray means the node is an ancestor you're still inside, so an edge to it closes a live loop. Black means you already climbed out of that subtree; the edge merely re-points into finished territory — no path currently loops back onto the stack.
Why must we run DFS from every unvisited vertex rather than just one?
A graph can split into disconnected pieces; a cycle can sit entirely inside a component your single DFS never reached. Iterating over all vertices guarantees every component is explored. See Depth-First Search.
Why is DFS cycle detection and not ?
The color/visited guard ensures each vertex is entered once, and each adjacency-list entry (edge endpoint) is scanned once. Work is proportional to vertices plus edges, not vertices squared.
Why does "no back edge" mean a directed graph can be topologically sorted?
A back edge is the only DFS edge type that points to an ancestor; without one, ordering nodes by decreasing finish time never places a node before something that must come after it. This is exactly the Topological Sort guarantee.
Why can Union-Find (DSU) replace DFS for undirected cycle detection but the two colors of DFS can't be mimicked by DSU?
DSU asks "are and already in the same connected set?" — if yes, this new edge closes a cycle. That works because undirected connectivity is symmetric. DSU has no concept of stack order or direction, so it cannot reproduce the Gray/Black distinction directed graphs need.
Why does the mnemonic "GRAY means STAY" only apply to the directed case?
"Stay on the stack" captures the live ancestor idea that defines a directed back edge. Undirected detection doesn't hinge on stack-liveness — it hinges on which visited node you reached (parent or not), so a different mnemonic (pardon the parent) governs it.
Edge cases
An empty graph (no vertices, no edges) — cycle or not?
No cycle. There is no path at all, let alone one returning to its start; the outer loop never runs and DFS returns nothing.
A single vertex with no edges — cycle?
No. DFS enters it, finds no neighbors, marks it finished. A lone node cannot loop.
A single vertex with a self-loop — cycle?
Yes. The self-loop is a one-edge cycle; it must be detected explicitly (the neighbor equals the node itself).
Directed graph with two nodes and edges and — cycle?
Yes, a 2-cycle. is Gray, is Gray, and is a back edge. This is the smallest simple directed cycle and precisely why the parent-trick is banned for directed graphs.
Undirected graph, two nodes, one edge — cycle?
No. From you reach ; from the only neighbor is , which is the parent and is skipped. A single edge between two nodes is a tree, not a cycle.
A fully disconnected graph of isolated vertices (no edges at all) — cycle?
No. With zero edges there is no path to close. Every DFS call finishes immediately with no neighbors to examine.
A directed graph that is one long chain with no back edge — cycle?
No — it's a DAG. Every node turns Black in order and no edge ever points to a Gray ancestor, so it topologically sorts cleanly.
Connections
- Depth-First Search — the traversal every trap above is built on.
- Topological Sort — the "no back edge" flip-side of directed detection.
- Union-Find (DSU) — the DSU-vs-DFS trap for undirected graphs.
- Back Edges and Edge Classification — vocabulary behind the Gray/Black traps.
- Strongly Connected Components — where finish-time reasoning goes next.
- Bipartite Checking — a sibling DFS-coloring application.