skip to content

In DFS over a directed module-import graph, why is a plain visited set not enough to detect a cycle?

level: middleimportance: must knowfreq 70%

answer

  1. one bit answers the wrong question
  2. seen before versus currently inside
  3. two paths into the same shared dependency
  4. grey equals the active recursion path
  5. back edge into grey closes the cycle

basics

~20 s

A visited mark only says a vertex was seen before; a cycle needs to know it is still on the current search path. Three colours separate unseen, in-progress and finished, and only an edge into an in-progress vertex proves a cycle.

solid answer

~50 s

A boolean mark carries one bit, and cycle detection needs two states out of it. Consider imports `A -> B`, `A -> C`, `B -> D`, `C -> D`: the search reaches `D` twice, yet nothing is circular. Report a cycle on every repeat visit and you false-positive on that diamond; silently skip every marked vertex and you miss real cycles, whose closing edge also points at a seen vertex. The fix is three colours: white for undiscovered, grey while the vertex is being explored — that is, while it sits on the current search path — and black once its subtree has finished. An edge into a grey vertex is a **back edge** and proves a cycle; an edge into a black vertex proves nothing. The grey set is the witness: it *is* the import chain you print. Cost stays O(V+E).

code

pseudocode · 16 lines
pseudocode
DFS-VISIT(u):
    color[u] = GREY
    for v in adj[u]:
        if color[v] == GREY:
            report cycle closed by edge (u, v)
        else if color[v] == WHITE:
            parent[v] = u
            DFS-VISIT(v)
        ...                      // BLACK: forward or cross edge, ignore
    color[u] = BLACK

DETECT-CYCLES(G):
    for u in V:  color[u] = WHITE
    for u in V:
        if color[u] == WHITE:
            DFS-VISIT(u)

go deeper

for a junior

Know that a repeat visit is not automatically a cycle, and that a shared dependency reached by two paths is the counterexample. Recall the three state names and that only the in-progress state signals trouble.

for a middle

Explain the invariant that grey equals the current recursion path, classify an edge by the colour of its target, and state that a directed graph is cyclic exactly when a search produces a back edge. Keep the cost at O(V+E).

for a senior

Show that the grey path is the cycle witness and return the offending chain, not a boolean. Know why the rule must be rewritten for undirected graphs and how parallel edges break a naive parent check.

for a principal

Decide what the detector owes its callers: fail the build on the first cycle or enumerate all of them, how to report chains developers can act on, and whether the check runs per commit or per release given graph size and build-latency budget.

## The one bit that is missing "Have I seen this vertex?" and "am I currently inside this vertex?" are different questions, and a single boolean can only answer the first. Cycle detection in a directed graph depends entirely on the second. Take a module dependency graph with imports `A -> B`, `A -> C`, `B -> D`, `C -> D`. The traversal enters `A`, goes down through `B` to `D`, finishes `D`, finishes `B`, comes back up and goes down `C`, and there meets `D` again. `D` is marked. Nothing is circular. Two behaviours fall out of a boolean mark, and both are wrong: - **Report on any repeat visit** → false positive on this diamond, and on every shared dependency in a real project, which is most of them. - **Silently skip anything marked** → you also skip the edge that closes a genuine cycle, because that vertex is marked too. Cycles go unreported. ## Three colours Give each vertex a state instead of a bit: - **White** — not yet discovered. - **Grey** — discovered, exploration in progress. The vertex has been entered and its neighbour loop has not finished. - **Black** — finished. Every vertex reachable through it has been fully explored. The key invariant: **at every instant, the grey vertices are exactly the vertices on the current path from the traversal's root to the vertex being expanded.** They are the active frames, in order. That is why the grey set is not merely a detector but a witness: when you find a back edge `u -> v` with `v` grey, the segment of the grey path from `v` down to `u`, plus that edge, is the cycle, and you can print `v -> ... -> u -> v` as the actual import chain a developer has to break. ## Edge classification With colours in hand, every edge `u -> v` inspected during the search falls into one of four kinds: | `v`'s colour when `u -> v` is inspected | edge kind | cycle? | | --- | --- | --- | | white | tree edge (the search descends) | no | | grey | **back edge** | **yes** | | black, discovered after `u` | forward edge | no | | black, discovered before `u` | cross edge | no | Only the grey row matters for cycle detection, which is why you never need to distinguish forward from cross edges to answer "is this graph acyclic?". A self-loop `u -> u` is a back edge too: `u` is grey when its own neighbour list is being scanned. ## The theorem underneath A directed graph contains a cycle if and only if any depth-first search over it produces a back edge. One direction is easy: a back edge plus the grey path closes a cycle. The other direction is the useful one — it says *any* search order finds a cycle if one exists, so you never have to worry about picking the right start vertices. Since one search reaches only what is reachable from its root, wrap it in an outer loop that starts a new search from every still-white vertex; the colours are shared, so the whole scan remains O(V+E). ## Cost Time is unchanged from a plain traversal: each vertex is expanded once, each adjacency entry inspected once, O(V+E). Space is Θ(V) for the colour array — two bits per vertex — plus the active path. A frequent alternative implementation keeps a boolean "finished" array and a separate "on current path" set, which is the same three states wearing different clothes; grey is precisely membership in the path set. ## Undirected graphs are a different problem Do not carry the three-colour rule over unexamined. In an undirected depth-first search every non-tree edge is a back edge, so the grey test would fire on the edge from a vertex straight back to the neighbour it was discovered from. The undirected rule is: a cycle exists if you meet an already-discovered vertex that is **not** the neighbour you came from — with a caveat for parallel edges, where two separate edges between the same pair genuinely are a cycle and the naive parent check would suppress it. ## Why this is the standard interview probe The wrong answer — "a visited set detects cycles" — is fluent, confident and produces code that passes on a tree-shaped test fixture. It fails the first time two modules share a dependency, which in a real import graph is immediate. Being able to say *which* re-visit means a cycle, and to hand back the offending chain rather than a bare boolean, is the whole content of the question.

  • Once a back edge is found, how do you report the actual chain of modules rather than just 'a cycle exists'?
    Walk the grey path. The grey vertices at that instant are exactly the current root-to-`u` path, so the cycle is the suffix of that path starting at the grey target `v`, closed by the edge `u -> v`. Keeping a parent pointer per vertex lets you climb from `u` back to `v` and emit `v -> ... -> u -> v`. A bare boolean is nearly useless to whoever has to break the cycle.
  • Does the answer change if the search starts from a different vertex, or covers the graph in a different order?
    No. A directed graph has a cycle if and only if any depth-first search over it yields a back edge — the theorem holds for every start vertex and every neighbour ordering. What does change is which specific cycle you find first and how the non-tree edges split between forward and cross. Since one search only reaches what is reachable from its root, iterate over all still-white vertices.
  • Why can't you reuse this exact rule on an undirected graph?
    Because in an undirected search every non-tree edge is a back edge, including the edge straight back to the vertex you were discovered from. The grey test would fire on every single edge. The undirected rule is instead: meeting an already-discovered vertex that is not the neighbour you arrived from means a cycle — with care around parallel edges, where two distinct edges between the same pair really do form one.

Grey vertices are the doors you have opened and not yet walked back out of. Bumping into a still-open door means you have looped; a closed door is just a room someone already finished.

saying these in an interview costs you the question

  • Claims a boolean visited set detects directed cycles
  • Reports a cycle on any second arrival at a vertex
  • Cannot distinguish a back edge from a cross edge
  • Thinks grey means merely discovered rather than in progress
  • Applies the directed grey rule unchanged to undirected graphs

context

resolving links…