BFS traversal

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

can u plz tell which test series this belongs to?

---

Made easy

---

https://gateoverflow.in/60074/bfs

Answer 1

Answer is D . All are true. 

BFS and DFS traversal are using for knowing the connected component of given graph.So , if a and b are in FIFO queue then must be a path between a and b. We can't say surely about the which one have more total edges then others because in a queue all are unvisited neighbour node of some node.   

Comments

https://gateoverflow.in/60074/bfs