Menu
I'm writing an algorithm for finding the second min cost spanning tree. my idea was as follows:
My question is: Will this work? Is there a better way perhaps to do this?
734
The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees.
Sort the edges in O ( E log , then find a MST using Kruskal in . For each edge not already in the MST, temporarily add it to the MST, creating a cycle. Find the edge with maximal weight in the cycle that is not equal to . Remove temporarily, creating a new spanning tree.
Can a graph have more than one minimum spanning tree? Yes, but this is only possible if there is (1) more than one spanning tree and (2) duplicate edge weights. For a spanning tree to be a minimum spanning tree, it must have the minimum total weight.
A Minimum Spanning Tree (MST) is a subset of edges of a connected weighted undirected graph that connects all the vertices together with the minimum possible total edge weight. To derive an MST, Prim's algorithm or Kruskal's algorithm can be used.
You can do this -- try removing the edges of the MST, one at a time from the graph, and run the MST, taking the min from it. So this is similar to yours, except for iterative:
192
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
