engineering recuitment NIC NIELIT Scientist B 2023 Mock Test Algorithms Graphs/Spanning Tree and Shortest Paths Shortest Paths
Which of the following statements is/are false ?
I. The Kruskal’s algorithm for determining minimum cost spanning tree with ‘n’ vertices and ‘m’ edges in the graph takes a time of O(m log n).
II. B.F.S & D.F.S can be used to find the connected components of a graph.
III. An offline algorithm responds to a sequence of service – requests, each associated with a cost.
IV. Shortest paths problem can be solved using matrix – multiplication
V. A connected graph G is biconnected if for any two vertices u & v of G, there are no distinct disjoint paths between ‘u’ & ‘v’.
1
I, III
2
III, IV, V
3
II, IV, V
4
III only