Noesis
3.5.5 · D5Graphs

Question bank — DFS — algorithm, stack - recursion, O(V+E), visited array

1,895 words9 min read↑ Back to topic

Two pictures ground everything that follows — how DFS dives and backtracks, and how the stack rises and falls as it does.

Figure — DFS — algorithm, stack - recursion, O(V+E), visited array
Figure — DFS — algorithm, stack - recursion, O(V+E), visited array

True or false — justify

True or false: DFS always visits vertices in increasing numeric order.
False. It follows edges, not labels; order depends on the adjacency lists. For graph[0] = [2, 1] it visits 0, then 2, then 1.
True or false: recursive DFS and iterative DFS always produce the exact same visit order.
False. The iterative version pushes neighbours then pops the last one first, so it often processes neighbours in reverse order compared to the recursive for loop. Both are valid DFS, just different orders.
True or false: DFS visits every vertex of the graph.
False in general — it only reaches vertices reachable from the start. To cover a disconnected graph you must relaunch from each still-unvisited vertex (that is how Connected Components are counted).
True or false: if a graph has no cycles you can safely drop the visited array.
False. A DAG (no cycles, but directed) can reach the same node by two different paths, so without visited you'd re-explore its whole subtree — still correct output but exponential time. Visited is about efficiency here, not just termination.
True or false: DFS on a tree needs no visited array at all.
True. A tree has no cycles and exactly one path to each node, so you can never arrive twice — following the parent pointer back is the only "revisit", and you simply don't follow it.
True or false: DFS is because each vertex scans edges.
False. It is . Each vertex is entered once and its edges are scanned once in total, so the edge work adds up to (or undirected) — it is summed across vertices, not multiplied by them.
True or false: on a graph with many vertices and zero edges, DFS cost is .
False. It is — you still mark and process each isolated vertex once. This is exactly why we write and never alone.
True or false: DFS uses less memory than BFS on the same graph.
Not always. Both are worst case. DFS peaks at the longest path depth; BFS — Breadth-First Search peaks at the widest level. On a long thin graph DFS uses more; on a bushy shallow graph BFS uses more.
True or false: marking a node visited after processing it is fine.
False. If you process first and mark later, a cycle can re-enter the node before the mark is set, causing infinite recursion. Marking must be the first line of explore(u).
True or false: the iterative stack can never contain the same vertex twice.
False. A vertex with two already-processed neighbours gets pushed twice before it is ever popped — which is exactly why you must re-check visited after popping, not only before pushing.

Spot the error

The bug: explore(u) scans neighbours first and sets visited[u] = True as the last line. Why does it break?
A cycle re-enters u before the flag is set, so recursion never terminates. Marking must happen on arrival, before any neighbour is explored.
The bug: iterative DFS marks nodes only when pushing, never re-checks on pop. Why is it wrong?
A node pushed by two different neighbours sits on the stack twice; without the pop-time if visited[u]: continue it gets processed twice, breaking the "exactly once" guarantee.
The bug: someone claims visited = [False] * len(graph) should be created inside explore so it resets each call. Why is that fatal?
Then every recursive call starts with a blank slate, no node ever stays marked, and the very first cycle loops forever. The array must be shared across the whole traversal.
The bug: to find connected components, code calls dfs(graph, u) for every u but creates a fresh visited array each time. What goes wrong?
Every launch re-explores everything, so the component count equals and the cost blows up. The visited array must persist across launches so each fresh unvisited u marks a genuinely new component.
The bug: a learner says "the visited check is redundant once I skip the parent I came from." Why isn't that enough?
Skipping only the immediate parent stops trivial back-and-forth, but a longer cycle (A -> B -> C -> A) still re-enters A through a non-parent edge. You need the full visited array, not just parent-avoidance.
The bug: someone writes for v in graph[u]: explore(v) with no if not visited[v]. What is the consequence?
Every neighbour is re-explored even if already visited, so any cycle recurses forever and even a DAG repeats work exponentially. The guard is what makes DFS linear.

Why questions

Why is backtracking "automatic" in DFS?
Because the stack (explicit or the call stack) already holds the path back — popping/returning takes you to the most recent unfinished vertex, which is precisely the last junction with unexplored branches.
Why does recursion "just work" for DFS without building a stack yourself?
The language's call stack is a LIFO stack of paused calls; returning from a function is exactly a pop, so recursion gives you DFS's backtracking for free.
Why does the edge work sum to in an undirected graph?
By the Handshake Lemma: each undirected edge touches two endpoints, contributing to each of their degrees, so . DFS scans each vertex's list once, meeting every edge from both ends.
Why does the iterative version pop instead of dequeue?
Popping takes the most recently pushed neighbour first (LIFO), which drives exploration deep along one branch. Dequeuing (FIFO) would spread out level-by-level — that's BFS — Breadth-First Search, not DFS.
Why does reversed DFS post-order give a valid Topological Sort?
"Post-order" means each vertex is stamped finished only after every vertex reachable from it is already finished. So a prerequisite always finishes later than the thing built on top of it — but wait, it finishes later only among its own descendants; across the DAG the vertex that everything depends on finishes last of all. Concretely, for A -> B -> C (A needed first), DFS finishes C, then B, then A, giving finish-order C, B, A. Reverse it to A, B, C — exactly the valid build order. The reversal turns "finished last = depended-on most" into "listed first".
Why can DFS detect a cycle but a plain visited array alone can't tell you which edge closes it?
A visited node might just be finished on another branch. Cycle Detection needs a third state ("currently on the recursion stack") — hitting a node still in progress is what proves a back edge and hence a cycle.

Edge cases

Edge case: DFS starting on an isolated vertex (no edges). What happens?
It marks and processes that one vertex, finds no neighbours (graph[u] is empty), and returns immediately. Cost for that launch, and it correctly forms a one-vertex component.
Edge case: DFS on the empty graph (zero vertices).
The for u in range(0) loop never runs; DFS does nothing and reports zero components. No error — it is the natural base case.
Edge case: a self-loop (edge from A to A). Does DFS loop forever?
No. On arriving at A you set visited[A] = True, so when the self-loop edge points back to A the if not visited[v] guard skips it. The visited array handles self-loops just like any cycle.
Edge case: a directed edge A -> B with no B -> A. Does DFS from B reach A?
No. DFS follows edge direction, so from B you cannot traverse A -> B backwards. Reachability is one-way in a directed graph; a separate launch from A would be needed.
Edge case: parallel edges (two edges both A -> B). Do they cause a double visit?
No. The first edge marks B visited; the second edge's if not visited[B] fails and is skipped. They add to the edge count (and to in the bound) but never cause reprocessing.
Edge case: a graph that is one long chain of vertices. What's the recursion depth?
It reaches depth — every vertex is paused on the call stack simultaneously. This is the worst case for stack space () and can overflow the real call stack for very large , a reason to prefer the iterative version there.

Connections

  • BFS — Breadth-First Search — contrast every "why pop / LIFO" trap with FIFO behaviour.
  • Stack data structure — the LIFO engine behind backtracking.
  • Recursion and the Call Stack — why the recursive version needs no hand-built stack.
  • Cycle Detection — the "third state" edge cases above.
  • Topological Sort — the reversed post-order reasoning.
  • Connected Components — the shared-visited relaunch traps.
  • Handshake Lemma — the counting question.