We are provided with an undirected connected graph such that weight of all the edges is equal to some constant k. We wish to find the shortest distance between given pair of nodes.
Now we know that BFS is used to find the shortest distance between one node to every other node no matter it contains cycle or not Time will be O(e+v) only.
Now Take each statement:
I. We can use Depth First Search to determine the length of the shortest path between the pair of nodes. It may be the case DFS fails i.e. when a graph has cycle then DFS may result incorrect i.e.
It can give distance between 2 - 5 as 2,1,4,3,5 = 4 which is incorrect , correct is 2,6,5 = 2.
II. We can use Breadth First search to find the desired answer. This is true since we go level by level so we will get the shortest path between every other node from a particular node.
III. Breadth First Search will give the correct answer only if the given graph is a tree. This is note true since for cyclic graph also we will get correct answer.
IV. Depth First Search will give the correct result only if the given graph is a tree. This is true since there is no cycle in graph i.e.tree so we have only one way to reach desired node i.e. we will get correct distance only.