chap graphs /compute minimal-cost spanning tree static void prim(graph gint sint[dint[vfor (int = < () ++/initialize [iinteger max valued[ for (int = < () ++/process the vertices int minvertex(gd) setmark(vvisited)if ( !saddedgetomst( [ ] )if ( [ =integer max valuereturn/unreachable for (int first( ) () next(vw)if ( [wg weight(vw) [wg weight(vw) [wvfigure an implementation for prim' algorithm figure shows an implementation for prim' algorithm that searches the distance matrix for the next closest vertex for each vertex iwhen is processed by prim' algorithman edge going to is added to the mst that we are building array [istores the previously visited vertex that is closest to vertex this information lets us know which edge goes into the mst when vertex is processed the implementation of figure also contains calls to addedgetomst to indicate which edges are actually added to the mst alternativelywe can implement prim' algorithm using priority queue to find the next closest vertexas shown in figure as with the priority queue version of dijkstra' algorithmthe heap' elem type stores dijkelem object prim' algorithm is an example of greedy algorithm at each step in the for loopwe select the least-cost edge that connects some marked vertex to some unmarked vertex the algorithm does not otherwise check that the mst really should include this least-cost edge this leads to an important questiondoes prim' algorithm work correctlyclearly it generates spanning tree (because each pass through the for loop adds one edge and one unmarked vertex to the spanning tree until all vertices have been added)but does this tree have minimum costtheorem prim' algorithm produces minimum-cost spanning tree proofwe will use proof by contradiction let (vebe graph for which prim' algorithm does not generate an mst define an ordering on the vertices according to the order in which they were added by prim' algorithm to the mst