In [1]:
n = 7
edges = [[1,2,14], [1,3,10],[1,4,6], [1,5,19],
        [2,3,5],[2,4,7],[2,5,20], 
        [3,4,4], [3,5,17],[3,7,15], 
        [4,5,11], [4,6,7],[4,7,12],
        [5,6,21],[6,7,11]]
print(len(edges))
print(edges)

15
[[1, 2, 14], [1, 3, 10], [1, 4, 6], [1, 5, 19], [2, 3, 5], [2, 4, 7], [2, 5, 20], [3, 4, 4], [3, 5, 17], [3, 7, 15], [4, 5, 11], [4, 6, 7], [4, 7, 12], [5, 6, 21], [6, 7, 11]]
In [2]:
sorted(edges)
Out[2]:
[[1, 2, 14],
 [1, 3, 10],
 [1, 4, 6],
 [1, 5, 19],
 [2, 3, 5],
 [2, 4, 7],
 [2, 5, 20],
 [3, 4, 4],
 [3, 5, 17],
 [3, 7, 15],
 [4, 5, 11],
 [4, 6, 7],
 [4, 7, 12],
 [5, 6, 21],
 [6, 7, 11]]

Hrany usporiadané podľa veľkosti (tretia hodnota prvku edges)

In [3]:
sorted(edges,key=lambda x:x[2])
Out[3]:
[[3, 4, 4],
 [2, 3, 5],
 [1, 4, 6],
 [2, 4, 7],
 [4, 6, 7],
 [1, 3, 10],
 [4, 5, 11],
 [6, 7, 11],
 [4, 7, 12],
 [1, 2, 14],
 [3, 7, 15],
 [3, 5, 17],
 [1, 5, 19],
 [2, 5, 20],
 [5, 6, 21]]

Na začiatku sú všetky vrcholy osamostatnené, reprezentujú sami seba

In [4]:
reprezentant = [i for i in range(n+1)]
hlbka = [0 for i in range(n+1)]
reprezentant[7] = 5
reprezentant[5] = 3
print(reprezentant)

[0, 1, 2, 3, 4, 3, 6, 5]
In [5]:
def find(x): #najde koren
    while x != reprezentant[x]:
        x = reprezentant[x]
    return x
In [6]:
find(7)
Out[6]:
3
In [7]:
def suSpojene(x, y): #vrati ci existuje cesta medzi nimi
    return find(x) == find(y)
In [8]:
suSpojene(7,5)
Out[8]:
True
In [9]:
def union(x, y): #spojenie dvoch komponentov
    reprezentant[find(x)] = find(y)

Kostra:

In [10]:
reprezentant = [i for i in range(n+1)]
kostra = []
for hrana in sorted(edges,key=lambda x:x[2]): #prejdeme vsetky hrany od najmensej
    v1, v2 = hrana[0], hrana[1] #v1 a v2 su vrholy hrany
    if not suSpojene(v1, v2): #ak nie su spojene
        print("pridame hranu do kostry:", hrana)
        kostra.append(hrana) #pridame do kostry
        union(v1, v2) #spojime
print(kostra)
print(sum(h[2] for h in kostra)) #cena kostry
print(reprezentant)

pridame hranu do kostry: [3, 4, 4]
pridame hranu do kostry: [2, 3, 5]
pridame hranu do kostry: [1, 4, 6]
pridame hranu do kostry: [4, 6, 7]
pridame hranu do kostry: [4, 5, 11]
pridame hranu do kostry: [6, 7, 11]
[[3, 4, 4], [2, 3, 5], [1, 4, 6], [4, 6, 7], [4, 5, 11], [6, 7, 11]]
44
[0, 4, 4, 4, 6, 7, 5, 7]
In [11]:
def find(x): #najde koren s kompresiou cesty
    while x != reprezentant[x]:
#        par = reprezentant[x]
#        reprezentant[x] = reprezentant[par] #aktualizujeme/skratime cestu
#        x = par                
        reprezentant[x], x = reprezentant[reprezentant[x]], reprezentant[x] #aktualizujeme/skratime cestu
    return x
In [12]:
reprezentant = [i for i in range(n+1)]
kostra = []
for hrana in sorted(edges,key=lambda x:x[2]): #prejdeme vsetky hrany od najmensej
    v1, v2 = hrana[0], hrana[1] #v1 a v2 su vrholy hrany
    if not suSpojene(v1, v2): #ak nie su spojene
        print("pridame hranu do kostry:", hrana)
        kostra.append(hrana) #pridame do kostry
        union(v1, v2) #spojime
print(kostra)
print(sum(h[2] for h in kostra)) #cena kostry
print(reprezentant)

pridame hranu do kostry: [3, 4, 4]
pridame hranu do kostry: [2, 3, 5]
pridame hranu do kostry: [1, 4, 6]
pridame hranu do kostry: [4, 6, 7]
pridame hranu do kostry: [4, 5, 11]
pridame hranu do kostry: [6, 7, 11]
[[3, 4, 4], [2, 3, 5], [1, 4, 6], [4, 6, 7], [4, 5, 11], [6, 7, 11]]
44
[0, 7, 7, 7, 7, 7, 7, 7]
In [13]:
def union(x, y): #spojenie dvoch komponentov podla hlbky
    #reprezentant[find(x)] = find(y)        
    
    rx, ry = find(x), find(y)
    if hlbka[rx] < hlbka[ry]:
        reprezentant[rx] = ry
        #hlbka[ry] = max(hlbka[ry], 1+hlbka[rx]) #nemusi
    else:    
        reprezentant[ry] = rx
        hlbka[rx] = max(hlbka[rx], 1+hlbka[ry])