Source code online books for professionals by professionals

Listing 7-4.  Kruskal’s Algorithm
def find(C, u):
    if C[u] != u:
        C[u] = find(C, C[u])                    # Path compression
    return C[u]
 
def union(C, R, u, v):a
    u, v = find(C, u), find(C, v)
    if R[u] > R[v]:                             # Union by rank
        C[v] = u
12
We’re sorting m edges, but we also know that m is O(n
2
), and (because the graph is connected), m is W(n).  
Because Q(lg n
2
) = Q(2.lg n) = Q(lg n), we get the result.

---

Chapter 7 
■
 Greed Is Good? prove It! 
153
    else:
        C[u] = v
    if R[u] == R[v]:                            # A tie: Move v up a level
        R[v] += 1
 
def kruskal(G):
    E = [(G[u][v],u,v) for u in G for v in G[u]]
    T = set()
    C, R = {u:u for u in G}, {u:0 for u in G}   # Comp. reps and ranks
    for _, u, v in sorted(E):
        if find(C, u) != find(C, v):
            T.add((u, v))
            union(C, R, u, v)
    return T
 
All in all, the running time of Kruskal’s algorithm is 
Θ(m lg n), which comes from the sorting.
Note that you might want to represent your spanning trees differently (that is, not as sets of edges). The algorithm 
should be easy to modify in this respect—or you could just build the structure you want based on the edge set T.
Note
 
■
  the subproblem structure used in Kruskal’s algorithm is an example of a matroid, where the feasible partial 
solutions are simply sets—in this case, cycle-free edge sets. For matroids, greed works. here are the rules: all subsets of 
feasible sets must also be feasible, and larger sets must have elements that can extend smaller ones.
Prim’s Algorithm
Kruskal’s algorithm is simple on the conceptual level—it’s a direct translation of the greedy approach to the spanning 
tree problem. As you just saw, though, there is some complexity in the validity checking. In this respect, Prim’s 
algorithm is a bit simpler.
13
 The main idea in Prim’s algorithm is to traverse the graph from a starting node, always 
adding the shortest edge connected to the tree. This is safe because the edge will be the shortest one crossing the cut 
around our partial solution, as explained earlier.
This means that Prim’s algorithm is just another traversal algorithm, which should be a familiar concept if you’ve 
read Chapter 5. As discussed in that chapter, the main difference between traversal algorithms is the ordering of 
our “to-do” list—among the unvisited nodes we’ve discovered, which one do we grow our traversal tree to next? In 
breadth-first search, we used a simple queue (that is, a deque); in Prim’s algorithm, we simply replace this queue with 
a priority queue, implemented with a heap, using the heapq library (discussed in a “Black Box” sidebar in Chapter 6).
There is one important issue here, though: Most likely, we will discover new edges pointing to nodes that are 
already in our queue. If the new edge we discovered was shorter than the previous one, we should adjust the priority 
based on this new edge. This, however, can be quite a hassle. We’d need to find the given node inside the heap, change 
the priority, and then restructure the heap so that it would still be correct. You could do that by having a mapping from 
each node to its position in the heap, but then you’d have to update that mapping when performing heap operations, 
and you could no longer use the heapq library.
13
Actually, the difference is deceptive. Prim’s algorithm is based on traversal and heaps—concepts we’ve already dealt with—while 
Kruskal’s algorithm introduced a new disjoint set mechanism. In other words, the difference in simplicity is mostly a matter of 
perspective and abstraction.

---

Chapter 7 
■
 Greed Is Good? prove It! 
154
It turns out there’s another way, though. A really pretty solution, which will also work with other priority-based 
traversals (such as Dijkstra’s algorithm and A*, discussed in Chapter 9), is to simply add the nodes multiple times. 
Each time you find an edge to a node, you add the node to the heap (or other priority queue) with the appropriate 
weight, and you don’t care if it’s already in there. Why could this possibly work?
We’re using a priority queue, so if a node has been added multiple times, by the time we 
•
remove one of its entries, it will be the one with the lowest weight (at that time), which is the 
one we want.
We make sure we don’t add the same node to our traversal tree more than once. This can be 
•
ensured by a constant-time membership check. Therefore, all but one of the queue entries for 
any given node will be discarded.
The multiple additions won’t affect asymptotic running time (see Exercise 7-17).
•
There are important consequences for the actual running time as well. The (much) simpler code isn’t only easier 
to understand and maintain; it also has a lot less overhead. And because we can use the super-fast heapq library, the 
net consequence is most likely a large performance gain. (If you’d like to try the more complex version, which is used 
in many algorithm books, you’re welcome, of course.)
Note
 
■
  re-adding a node with a lower weight is equivalent to a relaxation, as discussed in Chapter 4. as you’ll see,  
I also add the predecessor node to the queue, making any explicit relaxation unnecessary. When implementing dijkstra’s 
algorithm in Chapter 9, however, I use a separate 
relax
 function. these two approaches are interchangeable (so you 
could have prim’s with 
relax
 and dijkstra’s without it).
You can see my version of Prim’s algorithm in Listing 7-5. Because heapq doesn’t (yet) support sorting keys, as 
list.sort and friends do, I’m using (weight, node) pairs in the heap, discarding the weights when the nodes are 
popped off. Beyond the use of a heap, the code is similar to the implementation of breadth-first search in Listing 5-10. 
That means that a lot of the understanding here should come for free.