figure the running time of kruskal' algorithm we denote the number of vertices and edges of the input graph with and mrespectively because of the high level of the description we gave for kruskal' algorithm in code fragment analyzing its running time requires that we give more details on its implementation specificallywe should indicate the data structures used and how they are implemented we can implement the priority queue using heap thuswe can initialize in ( log mtime by repeated insertionsor in (mtime using bottom-up heap construction (see section in additionat each iteration of the while loopwe can remove minimum-weight edge in (log mtimewhich actually is (log )since is simple thusthe total time spent performing priority queue operations is no more than ( log nwe can represent each cluster using one of the union-find partition data structures discussed in section recall that the sequence-based union-find structure allows us to perform series of union and find operations in ( log ntimeand the tree-based version can implement such series of operations in ( logntime thussince we perform calls to method union and at most calls to findthe total time spent on merging clusters and determining the clusters that vertices belong to is no more than (mlognusing the sequencebased approach or (mlognusing the tree-based approach thereforeusing arguments similar to those used for dijkstra' algorithmwe conclude that the running time of kruskal' algorithm is ((nmlog )which can be simplified as (mlog )since is simple and connected