A BFS traversal from a source node s in an unweighted, connected and undirected graph results in
a BFS tree T. The tree T is a data structure for computing___
A.
the shortest path between every pair of vertices.
B.
the shortest path from S to only those nodes that are leaves of T.
C.
the shortest path from S to every vertex in the graph.
D.
the longest path from S to every vertex in the graph.
A published solution is not available for this question yet.
Let G = (V, E) be an undirected graph having distinct positive edge weights. Let V be partitioned
into two non-empty sets X and Y. Let e = (s, t) be the minimum cost edge, with s belonging to X and
t belonging to Y. Which of the following statement(s) is/are true?
1. There must be only one unique spanning tree with minimum weight for G.
2. The edge e must definitely belong to minimum cost spanning tree of G
A.
Only 1
B.
Only 2
C.
Both 1 and 2
D.
Neither 1 nor 2
A published solution is not available for this question yet.
Which of the following statements is **true** about Dijkstra's algorithm to find the shortest path?
A.
The shortest path returned by Dijkstra's algorithm always passes through the
least number of vertices.
B.
To decide which node to visit next, Dijkstra's algorithm selects the node with
smallest known distance.
C.
Dijkstra’s algorithm may fail for graphs with negative weights because it does
not reconsider a node once it marks it as visited even if a shorter path exists than the previous
one.
D.
It returns the shortest path between all pairs of nodes.
A published solution is not available for this question yet.
Based on the above data, answer the given subquestions.
A.B.C.D.
**DBMS**
**Section Id :** 64065329425
**Section Number :** 9
**Section type :** Online
**Mandatory or Optional :** Mandatory
**Number of Questions :** 25
**Number of Questions to be attempted :** 25
**Section Marks :** 50
**Display Number Panel :** Yes
A published solution is not available for this question yet.