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

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.