prim-pseudo.py [download]

#
# This is pseudo-code for Prim's algorithm
# NOT PYTHON
#

def prim(G=(V,E), w):
    cost[*] = infinity
    prev[*] = nil

    u0 = any node from V
    cost[u0] = 0
    Q = make-priority-queue(V, cost)
    S = { }
    X = { }

    while Q is not empty:
        u = Q.deletemin()
        S = S \union {u}
        if prev[u] is not nil:
            X = X \union {(prev[u], u)}
        for (u,v) in E && v not in S:
            if cost[v] > w(u,v):
                cost[v] = w(u,v)
                prev[v] = u
                Q.decrease-key(v, cost[v])
    return sum(cost), X
            

Last Updated 03/01/2024