Kruskal's Algorithm

Kruskal's algorithm is a popular algorithm for finding minimum spanning trees. Here is an outline of it:

(1) Start with an empty tree.

(2) If the current shortest edge connects two vertices that are unconnected in the tree you've constructed so far, then add the current shortest edge to the tree.

(3) Go to (2).

Here is my Python implementation of Kruskal's algorithm.

Kruskal's algorithm is a greedy algorithm. Put simply, a greedy algorithm always does what's best at that moment. You might think that all algorithms should do that, but sometimes locally optimal decisions don't lead to global optima. Fortunately, they do in this case.

Like I said in my post on disjoint-set data structures, Kruskal's algorithm uses a disjoint-set data structure. You assign each vertex a number from 0 to N - 1, where N is the number of vertices. Then you can use subset membership within the disjoint-set data structure to represent connection between vertices. Specifically, if the numbers for two vertices belong to the same subset, then the vertices are connected. This representation makes executing step (2) easy.