Given a undirected and connected graph, and the edges have weights of either 1 or 2 (actually it is also applicable for weight larger than 2). How can we find a MST of the graph by using BFS?
Ans (I guess):
First, we can view an edge with weight of 2 as two edges with weight of 1 connected together. Then we can simply apply BFS to solve this problem. After finish the BFS algorithm, we check all the edges originally with weight of 2. If both parts of an edge are not both chosen as a path of the MST, then we delete this path. Finally, the result is a MST.
Ans (I guess):
First, we can view an edge with weight of 2 as two edges with weight of 1 connected together. Then we can simply apply BFS to solve this problem. After finish the BFS algorithm, we check all the edges originally with weight of 2. If both parts of an edge are not both chosen as a path of the MST, then we delete this path. Finally, the result is a MST.
No comments:
Post a Comment