algorithm notes let (vewhich is represented by an adjacency list adj some support data structures is the forest - set of all (partialtrees mst is the minimum spanning treerepresented by set of edges is priority queue of edges kruskal( let be set of singleton set of all vertices in mst <{ < while not empty do (uv<extractmin( / is modified if find-set( !find-set(vthen /find-set(ireturns the set in /which vertex belongs to /this effectively does cycle check /if accepted begin merge(find-set( ),find-set( )in mst <mst union {(uv) end return mst proof of correctness let be connectedweighted graph and let be the subgraph of produced by the algorithm cannot have cyclesince the last edge added to that cycle would have been within one subtree and not between two different trees cannot be disconnectedsince the first encountered edge that joins two components of would have been added by the algorithm thusy is spanning tree of it remains to show that the spanning tree is minimallet be minimum spanning tree if then is minimum spanning tree otherwiselet be the first edge considered by the algorithm that is in but not in has cyclebecause you cannot add an edge to spanning tree and still have tree this cycle contains another edge which at the stage of the algorithm where is added to yhas not been considered this is because otherwise would not connect different trees but two branches of the same tree then / is also spanning tree its total weight is less than or equal to the total weight of this is because the algorithm visits before and therefore (eps (fif the weights are equalwe consider the next edge which is in but not in if there is no edge leftthe weight of is equal to the weight of although they consist of different edge set and is also minimum spanning tree lovely professional university