Source code online books for professionals by professionals

Listing 7-5.  Prim’s Algorithm
from heapq import heappop, heappush
 
def prim(G, s):
    P, Q = {}, [(0, None, s)]
    while Q:
        _, p, u = heappop(Q)
        if u in P: continue
        P[u] = p
        for v, w in G[u].items():
            heappush(Q, (w, u, v))
    return P
 
Note that unlike kruskal, in Listing 7-4, the prim function in Listing 7-5 assumes that the graph G is an undirected 
graph where both directions are explicitly represented, so we can easily traverse each edge in both directions.
14
14
As I mentioned when discussing Kruskal’s algorithm, adding and removing such redundant reverse edges is quite easy, if you 
need to do so.

---

Chapter 7 
■
 Greed Is Good? prove It! 
155
As with Kruskal’s algorithm, you may want to represent the resulting spanning tree differently from what I do 
here. Rewriting that part should be pretty easy.
Note
 
■
  the subproblem structure used in prim’s algorithm is an example of a greedoid, which is a simplification and 
generalization of matroids where we no longer require all subsets of feasible sets to be feasible. sadly, having a greedoid 
is not in itself a guarantee that greed will work—though it is a step in the right direction.