example figure shows the first three steps of kruskal' algorithm for the graph of figure edge (cdhas the least costand because and are currently in separate mststhey are combined we next select edge (efto processand combine these vertices into single mst the third edge we process is (cf)which causes the mst containing vertices and to merge with mst containing vertices and the next edge to process is (dfbut because vertices and are currently in the same mstthis edge is rejected the algorithm will continue on to accept edges (bcand (acinto the mst the edges can be processed in order of weight by using min-heap this is generally faster than sorting the edges firstbecause in practice we need only visit small fraction of the edges before completing the mst this is an example of finding only few smallest elements in listas discussed in section the only tricky part to this algorithm is determining if two vertices belong to the same equivalence class fortunatelythe ideal algorithm is available for the purpose -the union/find algorithm based on the parent pointer representation for trees described in section figure shows an implementation for the algorithm class kruskalelem is used to store the edges on the min-heap kruskal' algorithm is dominated by the time required to process the edges the differ and union functions are nearly constant in time if path compression and weighted union is used thusthe total cost of the algorithm is th(|elog | |in the worst casewhen nearly all edges must be processed before all the edges of the spanning tree are found and the algorithm can stop more often the edges of the spanning tree are the shorter ones,and only about |vedges must be processed if sothe cost is often close to th(|vlog | |in the average case further reading many interesting properties of graphs can be investigated by playing with the programs in the stanford graphbase this is collection of benchmark databases and graph processing programs the stanford graphbase is documented in [knu exercises prove by induction that graph with vertices has at most ( - )/ edges prove the following implications regarding free trees (aif an undirected graph is connected and has no simple cyclesthen the graph has | edges