Micro-questions over the DFS module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. The idea

1. What is depth-first search?

Answer

A traversal that commits to exploring one branch all the way to its end before looking at any alternative.

2. Give the reading metaphor for depth-first.

Answer

Reading one book cover to cover, versus reading page one of every book on the shelf (which is breadth-first).

3. Describe the cave-explorer version.

Answer

Walk down a tunnel as deep as you can. At a dead end, backtrack to the last junction and try the other direction. When that junction is exhausted, backtrack further.

4. What is backtracking?

Answer

What the search does on reaching a vertex with no unvisited neighbours — return to the previous decision point and try the next option there.

5. Name three things DFS powers in software.

Answer

Puzzle solvers (Sudoku, N-Queens), dependency ordering (build systems), and cycle detection.


B. The vocabulary

6. What is the call stack, and how does recursive DFS relate to it?

Answer

The memory region holding one frame per started-and-not-yet-returned call, in LIFO order. Recursive DFS does not create a stack of its own — it borrows this one, which is why it is shorter to write and why it can run out of room.

7. What is an explicit stack, and what is the one real difference?

Answer

A stack you declare yourself, usually a plain list, holding the vertices still to examine. The difference: a list grows into ordinary heap memory and the call stack does not.

8. What is the visited set?

Answer

A set recording which vertices the search has already reached, consulted before descending into any vertex. The chalk mark on the cave wall.

9. On a cyclic graph, is the visited set an optimisation?

Answer

No. Without it the search never terminates. It is a correctness requirement, not a speed-up.

10. What is pre-order work, and when do you want it?

Answer

Work done for a vertex on arrival, before descending. Use it when a vertex’s answer depends on what is above it — its depth, or the route taken to reach it.

11. What is post-order work, and when do you want it?

Answer

Work done on departure, after every neighbour is fully explored. Use it when a vertex’s answer depends on what is below it — and it is the order topological sort is built on.


C. The two implementations

12. Write the shape of recursive DFS.

Answer
def dfs(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

13. Write the shape of iterative DFS.

Answer
stack = [start]
while stack:
    node = stack.pop()          # LIFO drives depth-first
    if node in visited: continue
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            stack.append(neighbor)

14. Which line makes iterative DFS depth-first rather than breadth-first?

Answer

stack.pop() — taking the most recently pushed vertex. Change it to popleft() and the same code is BFS.

15. Why does iterative DFS check if node in visited: continue after popping, rather than only before pushing?

Answer

A vertex can be pushed several times before it is first popped — by several different neighbours — so it must be re-checked at pop time. The pre-push check is only an optimisation.

16. When must you use the iterative version?

Answer

On extremely deep graphs — beyond roughly 1,000 levels in Python, where recursion triggers a RecursionError.

17. Do the recursive and iterative versions visit vertices in the same order?

Answer

Not necessarily. Both are valid DFS orders, but the iterative version pushes all neighbours before popping any, so it typically explores the last neighbour first unless you reverse the push order.


D. Applications

18. How do you detect a cycle in a directed graph with DFS?

Answer

Track the vertices currently in the active recursion — an in_stack set. Reaching a vertex already in_stack proves a cycle exists.

19. Why isn’t the plain visited set enough for directed cycle detection?

Answer

visited tells you a vertex was seen at some point, including on a finished branch. A cycle needs a vertex that is seen while still on the current path — which is what in_stack tracks.

20. How does DFS give a topological sort?

Answer

Run a post-order DFS on a DAG and reverse the finishing order. A vertex finishes only after everything it depends on has finished.

21. How do you count connected components with DFS?

Answer

Loop over all vertices. If a vertex is not in visited, increment a counter and run DFS from it to mark everything reachable.


E. Costs

22. Time complexity, and why?

Answer

— every vertex is visited once and every edge examined once.

23. Space complexity, and what makes it up?

Answer

— the visited set, plus stack depth in the worst case (a linear graph).

24. Why is the time not or ?

Answer

Because the visited set means no vertex is expanded twice, so the total neighbour-scanning across the whole run sums to .


F. Traps

25. What happens if you forget the visited set on a cyclic graph?

Answer

Infinite recursion — the search goes round the cycle forever.

26. What is Python’s default recursion limit, and what are the two fixes?

Answer

1,000. Either raise it with sys.setrecursionlimit(), or use the iterative implementation — which is the safer answer.

27. Does DFS find shortest paths?

Answer

No. It explores arbitrary deep paths first and may find a 10-hop route before ever considering a direct 1-hop one.

28. Why does BFS succeed where DFS fails at this?

Answer

BFS expands uniformly level by level, so the first path it finds is guaranteed to have the minimum number of edges.


G. Going further

29. How do you return the actual path rather than just whether one exists?

Answer

Track a parent map during the search — parent[child] = current — then walk it backwards from the goal at the end and reverse.

30. To find all paths, what must change, and why does it become exponential?

Answer

The visited mark must be un-marked on the way back out, so a vertex can appear on a different path later. That turns one traversal into an enumeration of every route, and the number of routes can be exponential in .

31. What is iterative deepening?

Answer

Depth-limited DFS run repeatedly with the limit increasing from 1. It finds the shortest path like BFS while using DFS’s memory.

32. What does iterative deepening cost for that memory saving?

Answer

Re-exploration — shallow levels are visited once per round. On a tree with branching factor the overhead is a constant factor of roughly , because the last level dominates the total.

33. Summarise DFS in one sentence.

Answer

Go deep, backtrack at dead ends, and mark where you have been — , memory proportional to depth, and no guarantee whatsoever about path length.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Traversal