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