chap graphs marked vertices vi vu vp unmarked vertices vi > "correctedge ej prim' edge vw vj figure prim' mst algorithm proof the left oval contains that portion of the graph where prim' mst and the "truemst agree the right oval contains the rest of the graph the two portions of the graph are connected by (at leastedges ej (selected by prim' algorithm to be in the mstand (the "correctedge to be placed in the mstnote that the path from vw to vj cannot include any marked vertex vi <jbecause to do so would form cycle (cb)(cd)and (cffrom these choicesthe least-cost edge from the mst is (cdso we add vertex to the mst for the next iterationour edge choices are (ae)(cb)(cf)and (dfbecause edges (cfand (dfhappen to have equal costit is an arbitrary decision as to which gets selected let' pick (cfthe next step marks vertex and adds edge (feto the mst following in this mannervertex (through edge (cb)is marked at this pointthe algorithm terminates kruskal' algorithm our next mst algorithm is commonly referred to as kruskal' algorithm kruskal' algorithm is also simplegreedy algorithm we first partition the set of vertices into |vequivalence classes (see section )each consisting of one vertex we then process the edges in order of weight an edge is added to the mstand the two equivalence classes combinedif the edge connects two vertices in different equivalence classes this process is repeated until only one equivalence class remains