1.5k views

Consider the tree arcs of a BFS traversal from a source node $W$ in an unweighted, connected, undirected graph. The tree $T$ formed by the tree arcs is a data structure for computing

1. the shortest path between every pair of vertices.
2. the shortest path from $W$ to every vertex in the graph.
3. the shortest paths from $W$ to only those nodes that are leaves of $T$.
4. the longest path in the graph.
edited | 1.5k views

BFS always has a starting node. It does not calculate shortest path between every pair but it computes shortest path between $W$ and any other vertex.
edited
+19
Yes, It does not calculate shortest path b/w any two vertices:-
A
/   \
B---C
(Here A, B and C forms a cycle, Graph is undirected as stated in question.)

Performing BFS on A, we get BFT of this graph-
A
/   \
B      C

In this BFT, distance between B to C is 2 (B-A-C) but actual shortest distance is one.
+1
So which option should be the answer?
0
If it was DFS instead of BFS, then would any given option satisfy?
0

No.
For DFS, no option would be correct.
Check this

BFS always produces shortest path from source to all other vertices in an unweighted graph.

So - B

+1 vote
Don't get confuse here between Prims algorithm and BFS.

We don't have any concern of edge weights in BFS. In prims algo we take edge weights in consideration.

So, if we traverse a graph using BFS we will get the shortest path from "Source" to every vertex in the graph.(here source is W).

Here path means no of edges.

Correct me if I'm wrong.

1
2