The GATE Grind

GATE 2014 CS (CS3) – Question 23

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 1 mark · Numerical answer

Depth-first search starts at an unknown vertex of the graph shown. A recursive visit is made only after checking that the vertex has not been visited. Find the maximum possible recursion depth, including the initial call.

Diagram for GATE 2014 CS (CS3) question 23

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 19 to 19

Explanation

A DFS stack follows a simple path. A19vertex path traverses all9left-grid vertices, the connector,8right-grid vertices and its pendant leaf. Visiting both grids excludes the connector’s pendant leaf; bipartite parity prevents traversing all9right-grid vertices from its entrance to the leaf’s attachment. Thus the maximum is **19**, including the initial call.