/prims' mst algorithmpriority queue version static void prim(graph gint sint[dint[vint /the current vertex dijkelem[ new dijkelem[ ()]/heap for edges [ new dijkelem( )/initial vertex minheap new minheap( ())for (int = < () ++/initialize [iinteger max value/distances [ for (int = < () ++/nowget distances do ( removemin()vertex()/get position while ( getmark( =visited) setmark(vvisited)if ( !saddedgetomst( [ ] )/add edge to mst if ( [ =integer max valuereturn/unreachable for (int first( ) () next(vw)if ( [wg weight(vw)/update [wg weight(vw) [wv/where it came from insert(new dijkelem(wd[ ]))figure an implementation of prim' algorithm using priority queue vn- let edge ei connect (vx vi for some let ej be the lowest numbered (firstedge added by prim' algorithm such that the set of edges selected so far cannot be extended to form an mst for in other wordsej is the first edge where prim' algorithm "went wrong let be the "truemst call vp ( jthe vertex connected by edge ej that isej (vp vj because is treethere exists some path in connecting vp and vj there must be some edge in this path connecting vertices vu and vw with and > because ej is not part of tadding edge ej to forms cycle edge must be of lower cost than edge ej because prim' algorithm did not generate an mst this situation is illustrated in figure howeverprim' algorithm would have selected the least-cost edge available it would have selected not ej thusit is contradiction that prim' algorithm would have selected the wrong edgeand thusprim' algorithm must be correct example for the graph of figure assume that we begin by marking vertex from athe least-cost edge leads to vertex vertex and edge (acare added to the mst at this pointour candidate edges connecting the mst (vertices and cwith the rest of the graph are (ae)