Spanning trees

Question

Suppose that a graph G has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to G?

Comments

Algorithm requires (E-1) passes hence O(E) time is required.

---

Suppose e has  the least edge weight among the new edges formed between G and the new vertex v

Then the new mst will be the (previous computed mst +e)

This would take O(E) time.

---

https://cs.stackexchange.com/questions/56486/finding-mst-after-adding-a-new-vertex

Answer 1

Apply prims algorithm here.Consider newly added vertex as starting vertex.So how will you proceed farther?You must take the least weighted edge adjacent to that vertex.After doing this you are done.Because the other component was MST already and now also overall spanning tree is minimum.