Question: An alternative minimum spanning tree algorithm is Kruskal's algorithm. In Kruskal's algorithm we take the lightest edge in the graph and place it into the spanning tree if it connects two vertices that haven't been connected yet. Then we take the second lightest edge and place it into the spanning tree if it connects two vertices that haven't been connected yet. We continue until all vertices are connected. Assume that we know how to check if two vertices are connected in O(1) time. How can we implement Kruskal's algorithm efficiently, and how much time will it take?
Answer: Insert all the edges into a heap in O(m log n) time. Now draw edges from the heap. Each heap removal takes O(log n) time. Processing each edge is a constant-time operation: if the vertices are already connected, we ignore the edge; if the vertices aren't, we add the edge to the tree. We remove at most m edges from the heap, so the total time taken is O(m log n).