kruskal-pseudo.py [download]

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

def kruskal(G=(V,E), w):
    DJ = make-disjoint-set()
    for u in V:
        DJ.makeset(u)
    cost = 0
    X = { }
    E1 = E sorted by ascending weight.

    for (u,v) in E1:
        if DJ.find(u) != DJ.find(v):
            X = X \union {(u,v)}
            DJ.union(u,v)
            cost += w(u,v)

    return cost, X
            

Last Updated 03/06/2024