Kruskal's algorithm

Kruskal's algorithm builds a minimum spanning tree the way a thrifty contractor would: always buy the cheapest cable still available, unless it would be wasteful. Sort all the cables from cheapest to most expensive, then go down the list one by one. Add a cable if it connects two parts of the network that are not yet linked; skip it if both its ends are already in the same connected piece, because adding it would just make a redundant loop. When everything is connected, you are done.

Step by step: sort all E edges by weight in increasing order. Maintain a collection of connected components, initially each vertex alone. Scan the sorted edges; for edge (u, v), if u and v are in different components, add the edge to the tree and merge their components; if they are already in the same component, discard it. Stop after adding V-1 edges. Why is this correct? Each accepted edge is the cheapest edge crossing the cut that separates the two components it joins (every cheaper edge was already scanned and would have merged those components earlier), so the cut property says it is safe. Each rejected edge is the heaviest on the cycle it would close, so the cycle property says it is safely skipped. The fast component test is union-find; with it, the running time is dominated by the sort: O(E log E) = O(E log V).

Kruskal's shines on sparse graphs and whenever the edges arrive already sorted or are cheap to sort. It is a textbook example of a provably correct greedy algorithm — the proof is not hand-waving but a direct application of the cut and cycle properties (and, more deeply, the theory of matroids, of which graphic matroids are the MST case). The one efficiency caveat worth stating: the union-find data structure is what makes the 'are these two vertices already connected?' check nearly O(1); a naive connectivity check would make Kruskal's far slower than its O(E log E) headline.