-1
$\begingroup$

Can we construct minimum spanning tree for an undirected graph with distinct weights using bfs or dfs?

I have gone through many answers but each answer says something different and I am not convinced.

$\endgroup$
  • 1
    $\begingroup$ What do your answers say, do they provide an algorithm for MST using DFS/BFS for a graph with distinct weights? Could you be more specific and provide reference which source and what it claims? $\endgroup$ – fade2black Aug 20 '17 at 12:46
  • $\begingroup$ The question is not really well-defined. Note, however, that while DFS/BFS can be done in linear time, no such algorithm is known for MST. $\endgroup$ – Yuval Filmus Aug 20 '17 at 12:58
  • $\begingroup$ stackoverflow.com/questions/27650579/… . Many answers said not possible but some like above says it's possible. $\endgroup$ – Zephyr Aug 20 '17 at 13:13
  • 1
    $\begingroup$ Please spend some time to edit your question so that people could unambiguously answer your question. $\endgroup$ – fade2black Aug 20 '17 at 17:47
  • 1
    $\begingroup$ Why are you not convinced? It's easy to come up with counter examples for either algorithm. $\endgroup$ – Raphael Aug 20 '17 at 18:28
0
$\begingroup$

Briefly, the answer is no, we cannot construct minimum spanning tree for an un-directed graph with distinct weights using BFS or DFS algorithm. This post provides a counterexample.

Computing MST using DFS/BFS would mean it is solved in linear time, but (as Yuval Filmus commented) it is unknown if such algorithm exists. However, there is an expected-linear-time randomized algorithm computing the MST.

$\endgroup$

Your Answer

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

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