Data Structures and Algorithm(C Programmming) You are given a weighted undirected graph G = (V,E), where E and V denote set of edges and vertices, and a minimum spanning tree T of that graph G. Answer...

You are given a weighted undirected graph G = (V,E), where E and V denote set of edges and vertices, and a minimum spanning tree T of that graph G. Answer the following questions about G and T on minimum spanning trees.

(a) Suppose we decrease the weight of one of the edges in G that is not among the edges in T. Suggest an algorithm in plain English that determines whether T is still a minimum spanning tree, and if it is not, calculates a minimum spanning tree of G. Explain the running time of your algorithm. (Note: Your algorithm should be faster than Prim’s and Kruskal’s)

(b) Consider the following algorithm running on G = (V,E). Would it calculate a valid MST of G? If yes, explain your reasoning in plain English, if no, provide a counter example graph that the algorithm will fail producing an MST. Also, what is the running time of the algorithm in the previous question. Show your analysis.