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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.