engineering recuitment NIC NIELIT Scientist B 2023 Mock Test Algorithms Graphs/Spanning Tree and Shortest Paths Graph Search
Consider the following set of statements:
S1: In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. There are n-k connected components in G.
S2: A depth-first search necessarily finds the shortest path between the starting point and any other reachable node.
S3: The depth-first tree on the simple undirected graph never contains a cross edge.
Which of the given statements is false?
1
Only S2
2
Only S3
3
Both S2 and S3
4
Both S1 and S2