bos bos ord jfk bwi lax pvd jfk sfo dfw dfw lax sfo ord pvd bwi mia mia ( (nfigure example of an execution of kruskal' mst algorithm (continuedthe edge considered in (nmerges the last two clusterswhich concludes this execution of kruskal' algorithm (continued from figure the running time of kruskal' algorithm there are two primary contributions to the running time of kruskal' algorithm the first is the need to consider the edges in nondecreasing order of their weightsand the second is the management of the cluster partition analyzing its running time requires that we give more details on its implementation the ordering of edges by weight can be implemented in ( log )either by use of sorting algorithm or priority queue if that queue is implemented with heapwe can initialize in ( log mtime by repeated insertionsor in (mtime using bottom-up heap construction (see section )and the subsequent calls to remove min each run in (log mtimesince the queue has size (mwe note that since is ( for simple grapho(log mis the same as (log nthereforethe running time due to the ordering of edges is ( log nthe remaining task is the management of clusters to implement kruskal' algorithmwe must be able to find the clusters for vertices and that are endpoints of an edge eto test whether those two clusters are distinctand if soto merge those two clusters into one none of the data structures we have studied thus far are well suited for this task howeverwe conclude this by formalizing the problem of managing disjoint partitionsand introducing efficient union-find data structures in the context of kruskal' algorithmwe perform at most find operations and union operations we will see that simple union-find structure can perform that combination of operations in ( log ntime (see proposition )and more advanced structure can support an even faster time for connected graphm > and thereforethe bound of ( log ntime for ordering the edges dominates the time for managing the clusters we conclude that the running time of kruskal' algorithm is ( log