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

3 Answers

+35 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 (59.4k points)
edited by
Yes, It does not calculate shortest path b/w any two vertices:-
    /   \
(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-
    /   \
  B      C

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

For DFS, no option would be correct.
Check this

If it was DFS instead of BFS and the given graph is acyclic also then would any given option satisfy?
we will perform bfs starting from b as root node so our distance will be 1 from b to c

@K ANKITH KUMAR, in that case options $(A),(B) \; and \; (D)$ will be true.

Since , graph is acyclic(circuit-less) , connected,undirected and unweighted. So , It must be Tree.

Now, if we apply DFS , then resulting tree will have the same structure as original tree , only difference is , resulting tree will be rooted on that node for which we have applied DFS.

Since , There is exactly one path or unique path between every pair of vertices in tree. So , shortest path will also be unique b/w every pair of vertices in a tree. In case of cyclic graph , there must be 2 paths b/w 2 vertices. So , one path may be longer than other path and if DFS traversal follows that path then it will give wrong result but it is not the case with tree.

For Example , PFA !


Here , we can find shortest path from  every other node to $B$ through parent pointer. For example , for example , we have to find shortest path from $B$ to $H$ , then using  DFS traversal , it will be $B\rightarrow D\rightarrow H$ , Now using parent pointer , we can go back to B as  $H\rightarrow D\rightarrow B$ and we will find the length of it. So, option (B) will be true in that case.

Similarly , to find the distance b/w any 2 node , we will check the children of one node , if destination node is not found then check its siblings and if again not found then will check children of grandparent.we repeat this procedure until we find the destination node for which we are finding shortest path. so option (A) is also true.

We can also find the longest path in a tree. check here and here. So, $(D)$ will also be true in that case.

+10 votes

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

So - B

answered by Loyal (9.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 (83 points)

Related questions

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
47,925 questions
52,325 answers
67,785 users