Answer Happy

7. As shown in the following figures, Prim's algorithm is usually used to find the minimum spanning tree, in which the intermediate set of edges X always forms a subtree, and S is chosen to be the set of this tree's vertices. On each iteration, the subtree defined by X grows by one edge, namely the lightest edge between a vertex in S and a vertex outside S. Draw a table to show the changes of cost and prev values, and construct the final Minimum Spanning Tree. (15') 8 4 A F 2 2 2 B procedure prim (G, w) Input: Output: for all u eV: cost(u) = ∞ prev(u) = nil Pick any initial node uo cost(u) = 0 H = makequeue (V) while H is not empty: v = deletemin(H) for each {v, 2} € E: D if cost (2) > w(v, 2): cost (2) = w(v, 2) prev(2) = v decreasekey(H,2) 1 10 2 G) 1 I 16 E H 2 A connected undirected graph G = (V, E) with edge weights we A minimum spanning tree defined by the array prev (priority queue, using cost-values as keys)