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

Can u please explain the meaning of this statement :

vertices a and b  are simultaneously on the FIFO queue at same point during the execution of breadth first search from s in an undirected graph.

I guess this should be possible only when I have both the vertices at the same distance from source vertex s , since it says about same point , what is significance of the word " same point " here ?

---

@ srestha , mam, 

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

 

ex:-

 

---

Actually it is asking for "statement is true" better if they asked "statement can be true"

In your example all 3 statement proved false.

That is not in option

So, we proved all three can be correct

ok??

---

How 1 and 3 are false for my example..

every connected Graph, have a path between any pair of vertices. ===> Statement 3 is always true.

( if a graph is disconnected then you can't apply BFS, you have to apply BFT )

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. ===> atmost 1 means there can be possible of 0 ===> Statement 1 is true.

 

Actually it is asking for "statement is true" better if they asked "statement can be true"
 

if that is the case, 2 is also true... otherwise only 1 and 3 are TRUE 

---

why 3 is true?

in ur diagram is there a path from A to B?

---

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