Menu
I want to make a dynamic minimum spanning tree. I have an existing MS tree over n vertices and I add one more vertex and edges to all the existing vertices from this new vertex. How can I update the MST for the new graph efficiently? O(n) would be optimal. Can I also make delete vertex operation efficient?
817
A minimum spanning tree is a special kind of tree that minimizes the lengths (or “weights”) of the edges of the tree. An example is a cable company wanting to lay line to multiple neighborhoods; by minimizing the amount of cable laid, the cable company will save money. A tree has one path joins any two vertices.
Minimum spanning tree has direct application in the design of networks. It is used in algorithms approximating the travelling salesman problem, multi-terminal minimum cut problem and minimum-cost weighted perfect matching. Other practical applications are: Cluster Analysis.
If all edge weights in a connected graph G are distinct, then G has a unique minimum spanning tree. Proof: Let G be an arbitrary connected graph with two minimum spanning trees T and T0; we need to prove that some pair of edges in G have the same weight. The proof is essentially a greedy exchange argument.
O(n log n) using Kruskal's algorithm. The key idea is any edges not used in the original MST will not be used in the new MST either. So just sort the n new edges O(n log n), merge this sorted list with the list of edges of the old MST (which you kept in sorted order, right?) O(n), then run Kruskal's algorithm anew on the resulting sorted list of edges O(n)-ish.
112
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
