graph algorithms figure kruskal' algorithm after each stage formallykruskal' algorithm maintains forest-- collection of trees initiallythere are |vsingle-node trees adding an edge merges two trees into one when the algorithm terminatesthere is only one treeand this is the minimum spanning tree figure shows the order in which edges are added to the forest the algorithm terminates when enough edges are accepted it turns out to be simple to decide whether edge (uvshould be accepted or rejected the appropriate data structure is the union/find algorithm from the invariant we will use is that at any point in the processtwo vertices belong to the same set if and only if they are connected in the current spanning forest thuseach vertex is initially in its own set if and are in the same setthe edge is rejectedbecause since they are already connectedadding (uvwould form cycle otherwisethe edge is acceptedand union is performed on the two sets containing and it is easy to see that this maintains the set invariantbecause once the edge (uvis added to the spanning forestif was connected to and was connected to vthen and must now be connectedand thus belong in the same set the edges could be sorted to facilitate the selectionbut building heap in linear time is much better idea then deletemins give the edges to be tested in order typicallyonly small fraction of the edges need to be tested before the algorithm can terminatealthough it is always possible that all the edges must be tried for instanceif there was an extra vertex and edge ( of cost all the edges would have to be examined function kruskal in figure finds minimum spanning tree the worst-case running time of this algorithm is (|elog | |)which is dominated by the heap operations notice that since |eo(| | )this running time is