edited by
10,972 views
47 votes
47 votes

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 by

6 Answers

Best answer
65 votes
65 votes
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.

Correct Answer: $B$
edited by
12 votes
12 votes

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

So - B

2 votes
2 votes
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.
Answer:

Related questions

34 votes
34 votes
4 answers
2
go_editor asked Sep 26, 2014
12,116 views
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjac...
65 votes
65 votes
11 answers
4
Ishrat Jahan asked Nov 3, 2014
17,533 views
In a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is$k$$k+1$$n-k-1$$n-k$