0
$\begingroup$

I found the following question in my book and I have no clue on what the answer should be:

What is the condition on search graph so that BFS Algorithm for graph and BFS Algorithm for tree generate and expand identical nodes in the same order?

Please Note you don't have to write a proof as I will prove it myself and post under my question accordingly to help others in the future (completing your answer)

$\endgroup$
4
  • $\begingroup$ Please edit your question to credit the source where you encountered this question. See cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    May 21, 2023 at 21:41
  • $\begingroup$ We're not particularly looking for posts that consist solely of the text of an exercise-style task and a request for us to solve it. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    May 21, 2023 at 21:41
  • 3
    $\begingroup$ I doubt that the question is answerable without seeing how exactly your book defines "BFS Algorithm for graph" and "BFS Algorithm for tree". $\endgroup$
    – D.W.
    May 21, 2023 at 21:42
  • $\begingroup$ Just over the top of my head, if the graph is a tree, then BFS traversal would be same. $\endgroup$
    – Rinkesh P
    May 22, 2023 at 7:04

1 Answer 1

0
$\begingroup$

If given graph is a tree (in other words, if tnhe graph doesn't contain cycles/loop/self-edges/self-loops), then the BFS traversal (level order traversal) would be the same.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.