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.

Improve this question
$\endgroup$
10
  • 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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 18:28

3 Answers 3

Reset to default
1
$\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.

Improve this answer
$\endgroup$
1
$\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.

Improve this answer
$\endgroup$
4
  • $\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, 2019 at 8:59
  • $\begingroup$ sorry for the mistake. it has corrected now. $\endgroup$
    – Dinithi
    Nov 4, 2019 at 10:30
  • $\begingroup$ Can you explain why the answer is "can not"? $\endgroup$
    – Yuval Filmus
    Nov 4, 2019 at 12:39
  • $\begingroup$ explained above. $\endgroup$
    – Dinithi
    Nov 14, 2019 at 13:34
0
$\begingroup$

It is possible to find an MST of a connected, undirected, and weighted graph in linear time if you are given two facts:

  1. There is exactly one cycle in the graph
  2. You are given one of the vertices in this cycle

From here, you can use DFS and BFS to find the maximum weight edge (u, v) on the cycle, and return the edge set of G - (u, v) that represents the MST.

An MST of a graph with distinct weights will never include the max weight edge of a cycle.

Improve this answer
$\endgroup$

Your Answer

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

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