Teaching UGC NET Mock Test Series 2025 (Paper 1 & 2) Algorithms Graphs/Spanning Tree and Shortest Paths Graph Search
Consider the following statements:
A. In a weighted undirected tree G = (V, E, w), breadth-first search from a vertex s finds single-source shortest paths from s (via parent pointers) in O(V + E) time.
B. If a graph represents tasks and their inter-dependencies (i.e., an edge (u, v) indicates that u must happen before v happens), then the breadth-first search order of vertices is a valid order in which to tackle the tasks.
Which of the above is TRUE?
1
Only A
2
Only B
3
Both A and B
4
Neither A nor B