Why does depth-first search on a graph need a visited set when tree traversal does not?
answer
- trees have one path in, graphs do not
- what a cycle does to plain recursion
- same vertex reached by two different routes
- mark on entry, before the neighbour loop
- each vertex once, each adjacency list once
basics
~20 sGraphs can contain cycles and several paths to the same vertex, so an unguarded depth-first search revisits vertices and may recurse forever. Marking a vertex the moment it is discovered makes every vertex expand exactly once, giving O(V+E).
solid answer
~50 sA tree offers exactly one path from the root to any node, so recursion can never arrive somewhere it has already been. A general graph breaks that guarantee twice over. If it has a cycle, an unmarked depth-first search follows the cycle forever — finiteness of the graph does not help, because the walk enumerates *paths*, and a cyclic graph has infinitely many. Even with no cycle at all, a vertex reachable by many distinct paths gets expanded once per path: a chain of `k` diamond shapes has only about `3k` vertices but `2^k` source-to-sink paths, so the unmarked walk is exponential. Marking on discovery — before iterating neighbours, not after the recursive calls return — collapses both failures. Each vertex is then expanded once and each adjacency list scanned once, which is exactly the O(V+E) bound.
go deeper
Be ready to say in one breath that graphs have cycles and repeated paths, that the mark goes on at discovery, and that the traversal costs O(V+E). Expect to write the restart loop that labels every region.
Explain the accounting: one expansion per vertex, one adjacency-list scan per expansion, degrees summing to E or 2E. Know that an adjacency matrix turns the same traversal into Θ(V²), and that a linearly scanned visited list is an accidental quadratic.
Show the cycle-free failure too — a diamond chain with exponentially many paths and no cycle at all. In review, flag the marked-after-recursion variant, since it passes on acyclic test data and hangs on the first cyclic input.
Own the representation decision behind the bound: adjacency lists versus matrix versus an implicit neighbour function changes the constant, the memory footprint and whether O(V+E) is even achievable on the data you actually have.
## The guarantee a tree gives and a graph does not Depth-first traversal of a tree needs no bookkeeping because a tree provides exactly one path from the root to every node. Recursion into children can never land on a node the walk has already touched. A general graph withdraws that guarantee in two independent ways: it may contain cycles, and even when it does not, it may offer several distinct paths to the same vertex. An unguarded depth-first walk over such a graph is not a traversal of the vertices at all — it is an enumeration of the paths. ## Two distinct failures, not one **Cycle: non-termination.** With edges `u -> v`, `v -> w`, `w -> u`, an unmarked recursion cycles until the call stack is exhausted. It is worth being precise about why "the graph is finite, so it must stop" is wrong: the recursion is not enumerating vertices, it is walking paths, and the set of walks in a cyclic graph is infinite. **Multiple paths, no cycle: exponential repeated work.** Take a directed acyclic "diamond chain": a source `s`, then repeated gadgets where the current vertex points to two vertices that both point to the next joint. With `k` diamonds there are roughly `3k` vertices but `2^k` distinct paths from source to sink. An unmarked depth-first search terminates here — there is no cycle — but expands the final vertex `2^k` times. This is the failure people forget, because "visited sets are for cycles" is only half the story. ## Where the mark goes Mark a vertex at **discovery**: the instant the traversal enters it, before the neighbour loop begins. The common bug is marking after the neighbour loop returns; the mark then is not in place while the subtree is being explored, so an edge that comes back around re-enters the vertex and the cycle problem returns. If the emptiness check lives in the caller ("only recurse into unmarked neighbours") rather than at the top of the routine, remember that the starting vertex still has to be marked. ## What the mark costs, and an accidental quadratic The mark needs O(1) membership testing — an array or bitmap indexed by vertex identifier is the usual choice, sized Θ(V). A membership structure with linear scan turns every edge inspection into an O(V) search and quietly converts the whole traversal into O(V·(V+E)). This is one of the most common self-inflicted slowdowns in a first graph implementation. ## Why the bound is additive With the mark in place, each vertex is expanded at most once. Expanding a vertex `u` scans `u`'s adjacency list once, costing `deg(u)` edge inspections. Summing degrees over all vertices gives `E` in a directed graph and `2E` in an undirected one, because each undirected edge appears in both endpoints' lists. Total work is therefore proportional to `V + E`, and it is additive rather than multiplicative precisely because no adjacency list is ever scanned twice. The representation matters. Over an adjacency **matrix**, finding a vertex's neighbours costs Θ(V) regardless of how few neighbours it has, so the same traversal becomes Θ(V²) — dramatically worse on a sparse graph, and indistinguishable on a dense one. Space is Θ(V) for the mark array plus whatever is held for the path currently being explored. ## Restarting: labeling every region A single depth-first search reaches only what is reachable from its start vertex. To label every connected region — for instance, grouping same-coloured pixels of a scanned bitmap into regions, where a vertex is a pixel and an edge joins neighbouring pixels of the same colour — wrap the traversal in an outer loop over all vertices, starting a fresh search with a fresh label from each still-unmarked one. The loop looks nested, but the mark array is shared across all the restarts, so every vertex is still expanded exactly once and the total stays O(V+E). On an implicit grid graph nothing is materialised: neighbours are computed from coordinates, and with four-neighbour adjacency `E <= 2V`, so the whole labeling pass is linear in the number of pixels. ## What the mark does not do It does not tell you *why* a vertex was reached a second time. In a directed graph, distinguishing "this edge closes a cycle" from "this edge points into a region already finished" needs strictly more state than one boolean per vertex. And in an undirected graph, the edge from a vertex back to the neighbour it was discovered from always hits a marked vertex — that is completely normal and not evidence of anything.
- Where exactly should the vertex be marked — before exploring its neighbours, or after?Before. Mark at discovery, the instant the traversal enters the vertex and ahead of the neighbour loop. If you mark only after the recursive calls return, the vertex stays unmarked for the entire time its subtree is being explored, so any edge that comes back around re-enters it and the traversal can loop forever. Marking on entry is what makes the 'expanded at most once' claim true.
- Why is the running time O(V+E) rather than O(V x E)?Because nothing is ever rescanned. The mark guarantees each vertex is expanded once, and expanding it walks its adjacency list a single time at cost `deg(u)`. The degrees sum to `E` for a directed graph and `2E` for an undirected one, so the totals add rather than multiply. Over an adjacency matrix the neighbour scan costs Θ(V) per vertex instead, which is why that representation gives Θ(V²).
- How do you use DFS to label every connected region, not just the one containing the start vertex?Loop over all vertices; whenever you find one still unmarked, hand out a new region label and run a depth-first search from it that stamps that label on everything it reaches. The mark array is shared across the restarts, so each vertex is still expanded exactly once and the whole pass remains O(V+E) despite the outer loop.
Exploring a cave system without chalking the passages you have already walked: with loops you circle forever, and with two routes to the same chamber you map it twice.
saying these in an interview costs you the question
- Says an unmarked DFS terminates because the graph is finite
- Marks a vertex only after its recursive calls return
- Thinks visited marking matters only for cyclic graphs
- Calls the traversal O(V x E) by multiplying vertices and edges
- Stores visited vertices in a linearly scanned list