Teaching HPSC Lecturer (Technical) Mock Test 2024 Algorithms Graphs/Spanning Tree and Shortest Paths Graph Search
(i). A depth-first search of a directed graph always produces the same number of tree edges (i.e. independent of the order in which the vertices are provided and independent of the order of the adjacency lists).
(ii). Both DFS and BFS require \(\Omega(n)\) storage for their operation.
(iii) If we double the weight of every edge in the graph shortest path between any two vertices will not change.
(iv). Dijkstra’s algorithm may not terminate if the graph contains negative weight edges.
Which of the above statements is/are FALSE?
1
(i) and (ii) only
2
(ii) and (iii) only
3
(iv) only
4
(i) and (iv) only
5
Question Not Attempted