Binary tree

Question

What is maximum possible height of BFS tree,if BSF is run on complete bipartisan graph Km,n where m>=1,n>=1 and starting vertex is S

Answer 1

The height is $2$.

Let, $U$ & $V$ be two sets of vertices and $S\in U$. Then, all the vertices of $V$ are enqued making height = 1. All vertices are enqued because the graph is complete. After 1st dequeue, all vertices of $U$ are again enqued making height = 2. Now, all vertices have been into queue therefore no more increment in height possible.

Comments

not very clear,can u please elaborate probably with an example graph and the vertices U and V considered

---

Refer the example here to know how to find shortest path using BFS. $U$ & $V$ are two sets of vertices of Bipartite graph. 

---

this is a bipartite graph, bfs on this will give a height of 3 right ?

---

This is not complete Bipartite.

---

got it, i missed the word "complete"
thank you:)

---

@Aghori  "all vertices are enqueued bcz graph is complete  " but its complete bipartite so only connected one will be enqueued .

---

I'm not sure what you are asking. @bharti and yes, only connected will be enqueued (2times)

---

@ bharti 

 but its complete bipartite so only connected one will be enqueued

In the complete bipartite graph a vertex is connected to every other vertex in the other set.

So, for the first a vertex in set U is discovered all the vertex in the set V will be enqueued as all are connected to that vertex & none of them have been discovered so far.