breadth first search

Question

The max possible height of BFS tree , if BFS is run on a complete bipartite graph K_m,n where m>=1 , n>=1 with starting vertex S is

Answer 1

Max possible height corresponds to the spanning tree generated by the BFS of the complete bipartite graph K_m,n ..

Say we have  {v1 , v2 , v3 ......., v_m}  in one partition of vertices and { t1 , t2 , ....... , tn } in the other vertex set..

So DFS can be done as selecting vertex from one of the sets alternately..So say we start DFS from v1 , then we reach to t1 from v1 , then to v2 from t1 , then to t2 from v2 and so on..

This way we will have max height  =  number of edges [ because in each step we are traversing to a descendent not sibling ]

                                           =  m + n - 1   [ As number of vertices  =  m + n ]

Hence max height possible as far as DFS tree is concerned    =  m + n - 1.. 

For BFS, we can take one vertex in v1.. Now after that we push all its neighbors in the queue  which are in the vertex set 2..All of them will be pushed as it is a complete bipartite graph.. Hence max height in this case = 1.

Comments

Can you show with a diagramatic representation for K3,3 ??

---

This is the required graph ..Red line shows the bfs traversal :

---

thank you :)

---

it's complete bigraph and therefore max hieght must be 2.

---

your answer is right

but the above diagram is a complete bipartite graph only

how does BFS on it give a height of 2....??

---

in complete bigraph you will have all node in one set connect to all node in another set .

then take any node of one set as starting node and then perform bfs . you will get all nodes of another set  in 1st level of bfs tree  . now then take node from this level and perform bfs then you will get all node of first set on next level except the root node .

now all nodes are visited and we have tree with three levels resulting in hieght 2.

---

got it :)

what if DFS is performed? i think then it would be m+n-1

---

@Habibkhan

for BFS it should be 2 only...

what you have done is for DFS traversal

---

Yes for bfs max height is 2 here and for dfs traversal max height would  be m + n -1

Answer 2

max height of BFS tree traversal, if BFS is run on a complete bipartite graph(  ) should be 2 only bcoz it can be patitioned into two group of vertices.

Comments

Bipartite graph and corresponding bfs tree

Answer 3

Answer for BFS is 2 because bipartite is divided into two set of disjoints therefore each level is required to show each set of disjoints.