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 _________.
View worked solution
Answer: 19
The maximum recursion depth in a Depth First Search (DFS) corresponds to the number of vertices in the longest simple path that the search can traverse without backtracking.
For any graph with vertices:
- The maximum possible recursion depth (including the initial call) is at most , because each vertex is visited at most once.
- This maximum depth of is achievable if and only if the graph contains a Hamiltonian path (a simple path that visits every vertex exactly once).
By counting the vertices in the given graph, we find that there are exactly 19 vertices.
Since the graph is connected and contains a Hamiltonian path, a DFS starting at the beginning of this path can traverse all 19 vertices sequentially without backtracking. This results in a recursion stack containing all 19 vertices.
Therefore, the maximum possible recursion depth is 19.
Free practice · Your answers on this page are not saved.