Алгоритм Крускала

class edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w
        
def push(heap, e):
    i = len(heap)
    heap.append(e)
    while i > 1 and e.w < heap[int(i/2)].w:
        heap[i] = heap[int(i/2)]
        i = int(i/2)
    heap[i] = e

def pop(heap):
    if len(heap) < 2:
        return heap[0], heap
    item = heap[1]
    last = heap[len(heap)-1]
    heap = heap[0:len(heap)-1]
    parent = 1
    child  = 2
    while child < len(heap):
        if child < len(heap)-1 and \
           heap[child].w > heap[child+1].w:
            child += 1
        if last.w < heap[child].w:
            break
        heap[parent] = heap[child]
        parent = child
        child *= 2
    if len(heap) > 1:
        heap[parent] = last
    return item, heap

def makeset(V):
    p = [v for v in V]
    rank = len(V)*[0]
    return p, rank
    
def find(x, p):
    while x != p[x]:
        x = p[x]
    return x
    
def union(u, v, p, rank):
    ru = find(u,p)
    rv = find(v,p)
    if ru == rv:
        return p, rank
    if rank[ru] > rank[rv]:
        p[rv] = ru
    else:
        p[ru] = rv
        if rank[ru] == rank[rv]:
            rank[rv] += 1
    return p, rank

def kruskal(V, E):
    V.sort()
    p, rank = makeset(V)
    mhE =[edge(-1, -1, -1)]
    msp = list()
    for e in E:
        push(mhE, e)
    e, mhE = pop(mhE)
    while e.w >= 0:
        if find(e.u,p) != find(e.v,p):
            msp.append(e)
            p, rank = union(e.u, e.v, p, rank)
        e, mhE = pop(mhE)
    return msp
    
def TEST_kruskal():
    V = [i for i in range(7)]
    E = [edge(0,1,28), edge(1,2,16), edge(1,6,14),
         edge(2,3,12), edge(3,4,22), edge(3,6,18),
         edge(4,5,25), edge(4,6,24), edge(5,0,10)]
    msp = kruskal(V, E)
    for e in msp:
        print("("+str(e.u)+")-"+str(e.w)+"-("+str(e.v)+")")

Для сортировки рёбер использовал минимальную кучу (зубрил).

Разукрашено на tohtml.com