MST Algorithm. Here's an approach to finding a minimum spanning tree in a connected undirected graph G = (V, E) with weight function w: E . The main idea of this algorithm is to maintain a subgraph G' = (V, E') such that each component of G' is a tree. In each iteration of the outer loop we add some edges that merge some of the components together.

1. Let E' = empty set 2. Loop indefinitely { 3. Let G' = (V, E') 4. Run DFS on G'. During the DFS, label each vertex v with the root of the DFS tree that contains v. 5. Foreach DFS tree T { 6. find the smallest weight edge (u, v)  E such that u  T and v  T. 7. add (u,v) to E', unless (u,v) is already in E'. 8. if E' has V-1 edges, return 9. } /* end Foreach DFS tree */ 10. } /* end Loop indefinitely */

Note that line 6 refers to the original edge set E whereas lines 7&8 refer to the set E' of edges selected to be part of the minimum spanning tree.

For simplicity, assume that all edge weights are distinct. When all the edge weights are distinct, the minimum spanning tree is unique.

Answer the questions below:

a. Show how each iteration of the loop in lines 59 can be implemented to run in O( E ) time.

b. Argue that each iteration of the outer loop in lines 210 takes O(E) time.