-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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Can not. Because we do not use any scenario to find minimum path in DFS or BFS. we just visit all the nodes considering depth first or breadth first. We visit the node when we first met it according to DFS OR BFS. But there may be easiest paths to visit those nodes that we will not have chance to try in BFS. SO finding shortest path also not possible there. But when considering unweighted graph then you can use BFS to find minimum spanning tree. To obtain minimum spanning tree of a weighted graph you can use prim's algorithm.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Welcome to computer science! Please check your answer again. You wrote "unweighted" twice here, but I think you meant "weighted" in the last sentence. Also you might want to add further explanation how BFS works in unweighted graphs to obtain an MST. $\endgroup$ – ttnick Nov 4 '19 at 8:59
  • $\begingroup$ sorry for the mistake. it has corrected now. $\endgroup$ – user466720 Nov 4 '19 at 10:30
  • $\begingroup$ Can you explain why the answer is "can not"? $\endgroup$ – Yuval Filmus Nov 4 '19 at 12:39
  • $\begingroup$ explained above. $\endgroup$ – user466720 Nov 14 '19 at 13:34

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.