Add new edge to graph and find new spanning tree

Question

Suppose we are given the minimum spanning tree T of a given graph G (with n vertices and m edges) and a new edge e = (u, v) of weight w that we will add to G.

I) Check if T remains a MST or not. II) If not, give an efficient algorithm to find the minimum spanning tree of the graph G + e.

Answer 1

Your current MST T contains n-1 edges. The addition to your graph of the new edge e = (u,v) with weight w creates exactly one cycle C in the graph T + e (T with edge e added). If the new edge weight (w) is less than the weight of the highest-weight edge in this cycle C, then you can create a lower weight MST by replacing that higher-weight edge with e. Otherwise, your current MST remains optimal.

The algorithm is basically this:

1. Find the unique path P from u to v in T
2. Find the edge e* in P that has maximum weight w*
3. Is w < w*?
   • If so, then T' = T - e* + e is the MST for G + e,
     with weight(T') = weight(T) - w* + w
   • If not, then T' = T is the MST of G + e