The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
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.
asked in Algorithms by Veteran (99.8k points)
edited by | 1.5k views

3 Answers

+27 votes
Best answer
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.
answered by Veteran (55.1k points)
edited by
+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

+7 votes

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

So - B

answered by Loyal (8.3k points)
+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.
answered by (67 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,079 questions
45,571 answers
132,066 comments
49,040 users