1. Prims algorithm computes a minimum spanning tree of a connected, undirected graph G = (V,E) in which each edge (u, v) has a positive weight wt(u, v). It works as follows: Algorithm PRIMS ALGORITHM(G) T {v} (arbitrary vertex) while |T | < |V | do addtheshortestedge(a,b)withaT andb/T toT return T (a) Prove that the output of Prims algorithm is connected. (b) Prove that the output of Prims algorithm is a minimum spanning tree. (c) Describe in detail how you would implement the body of the while-loop. How do you find the shortest edge? What data structure(s) do you use? How are these initialized and updated? Give pseudo-code where relevant. (d) Analyze the running time of Prims algorithm, using the implementation details described in 1c. For full marks, your running time should be O(|E| log |V |) or better.