Kruskal's Algorithm Explained in more Detail

Let n be the number of vertices, and let m be the number of edges.

Create an array H of length m containing all the edges.  Each entry in this
array should contain the two vertices adjacent to the edge, plus the weight.

Heapify H, using the weight as the key.  This takes (m) time, or sort the
array, taking O(m log n) time.  (Remember that O(log n) and O(log m) are
the same if G is a connected graph.)

Initialize the forest F by making each vertex the root of a tree, namely
a leader, where the size of the set (the set of vertices in its tree) is 1.

Initialize T, the spanning tree, to be the empty set of edges.

Execute the following loop, until "Done".

  {
    Let {x,y} be the edge of smallest weight that has not yet been processed.
    Compute u = find(x) and v = find(y).  Be sure to use path compression
    in the code for find.

    If u = v, then discard the edge
    Else, both u and v are leaders.  If the number of followers of u is
    less than the number of followers of v, then make a pointer from u to
    v, an update the number of followers of v.  Otherwise, do the same thing
    with the roles of u and v reversed.  The number of trees in F will be
    decreased by 1, and add the edge {x,y} to T.

    If you are not done, reiterate the loop.
  }

    If the number of trees in F is more than 1, the graph is disconnected
    and has no spanning tree.  Otherwise, T will be a minimal spanning tree.

There are a number of tests for done.

	a) If there are no more edges, you are done.
	b2) If you have executed union(u,v) n-1 times, you are done.
        b3) If the number of trees of F is 1, you are done.
        b4) If, when you execute union(u,v), the number of followers of the
         new leader is n, you are done.

You don't need all these tests.  You do need a), and you do need just one
of the other three.  If one of the b conditions is true, you have found
a minimal spanning tree.

The time complexity is O(m log n), since the time it takes to heapify and
then repeatedly reheapify to find the lowest weight edge is O(m log n).
The time complexity of the union-find portion of the algorithm is
O(m alpha(n)), where alpha is the inverse of the Ackermann function, which
is smaller than log n, so the sum of the two is still O(m log n).