Suppose depth first search is executed on the graph below starting at some…
2014
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.
Attempted by 95 students.
Show answer & explanation
Correct answer: 19
Key idea: the maximum recursion depth of a recursive DFS equals the largest number of vertices on a root-to-leaf path in the DFS tree. We can achieve the maximum depth by choosing a start and edge-exploration order that makes the DFS follow a path that visits as many distinct vertices as possible before backtracking.
Count the vertices in the graph:
Left 3×3 block: 9 vertices
Right 3×3 block: 9 vertices
Single connector vertex between the two blocks: 1 vertex
Total vertices = 9 + 9 + 1 = 19.
How to achieve recursion depth 19:
Start DFS at a corner of one 3×3 block and explore that block in a Hamiltonian (snake-like) order so the recursion goes through all 9 vertices of the block without backtracking early.
From the last vertex of that block, continue to the single connector vertex, then proceed to the other 3×3 block and again traverse it in a snake-like order visiting all 9 vertices.
Because DFS only makes a recursive call for an unvisited vertex, this traversal yields a DFS recursion stack that reaches every vertex once before any backtracking. Therefore the maximum possible recursion depth (including the initial call) is 19.
A video solution is available for this question — log in and enroll to watch it.