About Kruskal's algorithm

So, I read the Kruskal algorithm from CLRS, and guess what? there are a lotta things to be remembered!

So, the implementation (pseudo code) of this algorithm is something like:
      MST-KRUSKAL($G$,$w$)

1.  $A = \phi$
2. for each vertex $v \in G.V$
3.       MAKE-SET($v$)
4. sort the edges of $G.E$ into nondecreasing order by weight $w$
5. for each edge $(u,v) \in G.E$, taken in nondecreasing order by weight
6.       if  FIND-SET($u$) $\neq$ FIND-SET($v$)
7.             $A = A \cup \{(u,v)\}$
8.             UNION$(u,v)$
9. return $A$ 

Implementation of sets is done via disjoint-set forests (section 21.3), which use union-by-rank and path-compression optimizations, to get a total running time of $O(m \alpha(n))$ where, $m$ is the total number of MAKE-SET, FIND-SET and UNION operations, and $n$ are the total MAKE-SET operations (which, obviously are always less than $m$).

Now, Kruskal algorithm basically connects two components of the graph $G$, via a light edge. This light edge is obviously safe to add, by using the corollary 23.2. So, initially there are $|V|$ trees, and at the end of the Algorithm, there is just one tree left, connecting all the vertices.

A word about the running time:

• Sorting in line 4 takes $O(E log E)$ time
• Since there are $|V|$ MAKE-SET operations ($n = |V|$), and $m = |V|+|E|$(not considering the constants multiplied to $|E|$), therefore running time comes out to be $$(|V|+|E|)\alpha(|V|)\\ = |E| \alpha(|V|)$$
• So, the total running time is $$O(|E|log|E|+|E|\alpha(|V|)) \\= O(|E|log|E|)$$