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.
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.
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.
It is possible to find an MST of a connected, undirected, and weighted graph in linear time if you are given two facts:
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.