Problem : MST

You are given a graph G(V, E) with distinct positive edge weights, and a minimum spanning tree T(V, ) with respect to these weights; you may assume G and T are given as adjacency lists. Now suppose the weight of a particular edge e E is modied from w(e) to a new value w(e). You wish to quickly update the minimum spanning tree T to reflect this change, without recomputing the entire tree from scratch. There are four cases. In each case give a linear-time algorithm for updating the tree.

(a)e and w(e)

(b)e and w(e)>w(e).

(c) e and w(e)

(d )e and w(e) > w(e).

Hint: DFS works in linear time.