Questions: Cycle Detection in Directed Graphs

Question 1

During a DFS-based cycle detection on a directed graph, the algorithm follows an edge and arrives at a vertex that has already been completely processed (colored black). What should the algorithm conclude?

• A. A cycle has been found, because the vertex was already visited
• B. No cycle is indicated — a finished vertex means its entire subtree was acyclic
• C. The graph contains a back edge, which always signals a cycle
• D. The algorithm has encountered a cross edge, which means the graph is disconnected

Answer: (B)

A black vertex has been fully processed — all its descendants were explored and no cycle was found in its subtree. Arriving at a black vertex through an edge simply means there is another path to an already-resolved part of the graph; this is perfectly consistent with a DAG (directed acyclic graph). Only encountering a gray vertex signals a cycle, because gray means 'currently on the active DFS path.' The three-color scheme exists precisely to distinguish these two cases: finished (black) vs. active ancestor (gray).

Question 2

Why is a two-color scheme (visited / unvisited) insufficient for cycle detection in directed graphs?

• A. Two colors cannot represent the starting vertex of DFS
• B. Two colors cannot distinguish a vertex that is a finished descendant from a vertex that is an active ancestor on the current path
• C. DFS requires at least three colors to handle disconnected graphs
• D. Two colors work for undirected graphs but directed graphs require more states due to edge directionality

Answer: (B)

The critical information is whether a vertex is an ancestor on the *current* DFS recursion stack (gray) or a fully processed vertex from a prior branch (black). With only two colors, both cases look the same: 'visited.' This causes false positives — the algorithm would report a cycle when DFS reaches any previously visited vertex, even one that was finished in an earlier branch and poses no cycle risk. The three-color scheme resolves this by keeping a 'currently being explored' state separate from 'fully done.'

Question 3

In DFS-based cycle detection on a directed graph, discovering a back edge (an edge pointing to a gray vertex) is both a necessary and sufficient condition for the graph to contain a cycle.

• T. True
• F. False

Answer: True

A back edge connects the current DFS path to one of its own ancestors — by definition this creates a cycle (you can follow the path from the ancestor down to the current vertex, then take the back edge back up). Conversely, if a directed graph has a cycle, any DFS traversal of it must encounter a back edge when it reaches a vertex already on the current recursion stack. So the two conditions are equivalent: back edge ↔ cycle.

Question 4

If DFS encounters an edge to a fully-processed (black) vertex, this indicates a cycle exists in the directed graph.

• T. True
• F. False

Answer: False

Only gray vertices signal cycles. A black vertex has been fully explored — its entire reachable subgraph was processed without finding a cycle, and it has returned from its DFS recursion. An edge to a black vertex is either a forward edge (to a descendant finished before the current vertex) or a cross edge (to a vertex in a completely separate DFS tree). Neither creates a cycle. The three-color insight is that 'visited' must be split into two states to avoid this confusion.

Question 5

Explain why encountering a gray vertex during DFS indicates a cycle, while encountering a black vertex does not, and why this distinction requires three colors rather than two.

Model answer: A gray vertex is currently on the active DFS recursion stack — it is an ancestor of the current vertex. An edge back to it means you can travel from the ancestor to the current vertex (via the path DFS took) and then from the current vertex back to the ancestor (via the back edge), forming a cycle. A black vertex, by contrast, has already been fully processed: DFS visited it, explored all its descendants, and returned. Reaching it again just means two paths converge on the same node — no loop is formed. Two colors cannot tell these apart because both are 'visited'; the third color (gray) preserves the 'still on the stack' information that makes cycle detection correct.

The three-color scheme encodes the state of the DFS call stack. Gray means 'open call frame' — we entered this vertex's DFS call but haven't returned yet. Black means 'closed call frame' — we have returned. A back edge leads to an open frame, meaning we're inside a recursive call that originated from that vertex, which is exactly a cycle. A cross/forward edge leads to a closed frame, meaning we've exited that call, so there's no loop.