doubt

Question

Comments

Take a small graph which is complete bipartite and run BFS on it, you will get 2 only.

---

How?.Please explain. :)

---

Answered!!

Answer 1

I have taken a small example here.

Lets consider K_4,3

The attached diagram shows the graph and the BFS tree.

Height = 2

Explanation: In a bipartite graph, the vertex set can be partitioned into two disjoint sets. Lets consider the two partitions as U and V. Lets take a vertex from partition U as source. Then the BFS tree will contain all the nodes of partition V in height 1, since the source is connected to all the vertices of V. Now, we take a vertex from V which appears in the BFS queue after the source. Since it is connected to all the vertices of U, we include all the vertices of U in height 2. 

Comments

Where r ur two partitions u and v in the second graph?

---

Second graph is the BFS tree.

In the first graph, U={A,B,C,D} V={E,F,G}

---

Awesome explanation..!! thank you..:)

---

gateset check this pls..https://gateoverflow.in/104654/hashing