607 views
1 votes
1 votes
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

1 Answer

Best answer
1 votes
1 votes
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.
selected by

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
3