Update minimum spanning tree if edge is added

Question

I have a possible solution for the following question, but not sure if correct:

Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly.

An edge is added to G to produce a new graph. Give an algorithm that uses T to find a minimum spanning tree for the new graph in O(|V|) time.

My algorithm:

for each vertex do
   if smallest edge not in T then
      replace this edge with existing edge in T
      break
   end if
end for

I do not have much experience in writing pseudocode, so my algorithm might be over-simplified or incorrect. Please correct me if I am wrong. Thanks!

Answer 1

Don't know if your algorithm is correct, but it doesn't seem O(|V|) at least, because getting the "smallest edge not in T" of a vertex cannot be done in O(1).

The most usual way to add an edge e=(u, v) into a MST T is:

• Run a BFS in T from u to v to detect the edge with maximum value in that path. (O(|V|))
• If that edge's weight is greater than the weight of the edge you're trying to add, remove that old edge and add the new one. Otherwise, do nothing, because the new edge would not improve the MST. (O(1)).

The rationale behind this solution is that simply adding the edge into T would create exactly one cycle, and to restore the MST property you have to remove the edge with maximum value from that cycle.