Can somebody explain the characteristics for a BFS Tree from a complete graph?. Thanks in advance. I would need the shape of the tree, explain me a little bit how the algorithm would work in this certain graph

  • 2
    $\begingroup$ Have you tried manually running the BFS algorithm on some small complete graphs? Say $K_4$, $K_5$, or $K_6$? This should give you a pretty good intuition on what the shape of the resulting BFS tree is (and then you can move on to proving that your intuition is correct). $\endgroup$ – Steven May 22 '20 at 10:59
  • $\begingroup$ I just need the theoretical shape and some characteristics of the tree not any specific number of vertex $\endgroup$ – user121501 May 22 '20 at 11:03
  • 2
    $\begingroup$ What I am saying is that you can get a pretty good guess on the general shape of the tree by observing the shape you obtain on some small instances. Then you can try to convince yourself that your guess is correct. $\endgroup$ – Steven May 22 '20 at 11:57
  • 2
    $\begingroup$ Program BFS and run it on several complete graphs, and see what you get. As simple as that. Don't expect us to spell out the answer for you. $\endgroup$ – Yuval Filmus May 22 '20 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy