Source code online books for professionals by professionals

Listing 7-3.  A Naïve Implementation of Kruskal’s Algorithm
def naive_find(C, u):                           # Find component rep.
    while C[u] != u:                            # Rep. would point to itself
        u = C[u]
    return u
 
def naive_union(C, u, v):
    u = naive_find(C, u)                        # Find both reps
    v = naive_find(C, v)
    C[u] = v                                    # Make one refer to the other
 
def naive_kruskal(G):
    E = [(G[u][v],u,v) for u in G for v in G[u]]
    T = set()                                   # Empty partial solution
    C = {u:u for u in G}                        # Component reps
    for _, u, v in sorted(E):                   # Edges, sorted by weight
        if naive_find(C, u) != naive_find(C, v):
            T.add((u, v))                       # Different reps? Use it!
            naive_union(C, u, v)                # Combine components
    return T
 
The naïve Kruskal works, but it’s not all that great. (What, the name gave it away?) In the worst case, the chain 
of references we need to follow in naive_find could be linear. A rather obvious idea might be to always have the 
smaller of the two components in naive_union point to the larger, giving us some balance. Or we could think 
even more in terms of a balanced tree and give each node a rank, or height. If we always made the lowest-ranking 
representative point to the highest-ranking one, we’d get a total running time of O(m lg n) for the calls to naive_find 
and naive_union (see Exercise 7-16).
This would actually be fine because the sorting operation to begin with is 
Θ(m lg n) anyway.
12
 There is one other 
trick that is commonly used in this algorithm, though, called path compression. It entails “pulling the pointers along” 
when doing a find, making sure all the nodes we examine on our way now point directly to the representative. The 
more nodes point directly at the representative, the faster things should go in later finds, right? Sadly, the reasoning 
behind exactly how and why this helps is far too knotty for me to go into here (although I’d recommend Sect. 21.4 in 
Introduction to Algorithms by Cormen et al., if you’re interested). The end result, though, is that the worst-case total 
running time of the unions and finds is O(m
a(n)), where a(n) is almost a constant. In fact, you can assume that a(n) ≤ 4, 
for any even remotely plausible value for n. For an improved implementation of find and union, see Listing 7-4.