BFS

Question

Consider two vertices a and b that are simultaneously on the FIFO queue at same point during the execution of breadth first search from s in an undirected graph.
Which of the following is true?
1. The number of edges on the shortest path between s and a is atmost one more than the number of edges on the shortest path between s and b.
2. The number of edges on the shortest path between s and a is atleast one less than the number of edges on the shortest path between s and b.
3. There is a path between a and b.

     a.1 only

     b.1 and 2 only

     c. 2 only

     d. 1, 2 and 3

Comments

https://gateoverflow.in/31929/question-of-bfs

Answer 1

Here (i) is satisfying condition 1 and 3

and (ii) is satisfying condition 2 and 3

Comments

MAM, it is undirected graph right ?

 just think A is root Node....

---

yes then 1 and 2 false

and I think 3 also can be false

point 3 will be more appropriate

 There is a undirected path between a and b.

right? 

---

You are applying BFS, therefore source is fixed (in the example S is source ),

but you are seeing in different view, That causes statement 3 is always true...

 

moreover note that, BFS can start from any vertex, there is no rule that you have to start from vertex

Answer 2

In BFS traversing we maintain a Queue to store nodes. Using the following loop we do bfs and push the nodes in the queue : 

while(!Q.empty()) {
        s = Q.front();
        //cout << s << " ";
        Q.pop_front();
        
        // while exploring the nodes of s we only push the adjacent nodes of s
        // explore adjacent loop
        for(i : i = adjacent nodes of s) {
            if(i is visited) {
                mark i as visited;
                // marking a node as visited does not mean fully explored
                Q.push(i);
            }
        }
    }

Queue makes it possible to push the nodes that are close to source earlier.

If we say that A is a node and it is at a distance d from the Source.While exploring (and pushing its adjacents in Queue) the adjacent nodes of A we touch a layer of nodes which are at distance of (d+1) from the source. (not more than that). And without completing (exploring) the layer of nodes at distance d from source we never explore a node which is at distance (d+1) from the source (how this even possible ? yes : because we are using queue not stack ) . This ensures that, whatever be the nodes in the queue in a particular time , the distance from source to any one of those nodes do not differ by more than 1.

conclusion:

distance[a] - distance[b] = 1,-1,0
// a and b are nodes in the queue in a particular time
// distance[a] = distance of a from source

Since a and b are in the queue, they are reachable from source S. There may or may not be direct path to go from a to b or b to a. We do not bother about that, because there is definitely a path via S :  a--to--S--to--b.

ALL ARE CORRECT.

Comments

@Debashish Deka  , sir, 

statement 2 is false. consider a and b are at same level.

 

ex:-

 

---

@Shaik Masthan you are right  when queue contain A,B 

difference between shortest path from S-A and S-B is 0.

hence statement 2 is false