DRDO CSE 2022 Paper 1 | Question: 33 (b)

Question

Consider the following graph.

How many nodes (apart from $s$) does the Depth First Search algorithm discover before discovering $t$ when starting from $s.$

Answer 1

We can see the graph can be divided into 4 vertical layers with 3 nodes in each layer. In each layer there is exactly one edge to the next layer and no way to go back or stay in the same layer. Hence starting from s, each layer will give us 4 nodes before we discover t.