algorithms-and-data-structures/Graph_Algorithms/Graph_Algorithms_Implementations/kruskal.py at master · behenate/algorithms-and-data-structures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Node:
    def __init__(self, val):
        self.val = val
        self.rank = 0
        self.parent = self


def find(x):
    if x != x.parent:
        x.parent = find(x.parent)
    return x.parent


def union(x, y):
    x = find(x)
    y = find(y)
    # Próba połączenia dwóch elementów z tego samego zbioru
    if x == y:
        return
    if x.rank > y.rank:
        y.parent = x
    else:
        x.parent = y
        if x.rank == y.rank:
            y.rank += 1


def kruskal(G, num_v):
    G = sorted(G, key=lambda x: x[2])
    n = len(G)
    A = [Node(i) for i in range(num_v)]
    for i in range(n):
        x = G[i][0]
        y = G[i][1]
        val = G[i][2]

        if find(A[y]) != find(A[x]):
            union(A[x], A[y])
            print("used", val, x, y)
    print(G)


G = [
    (0, 5, 1),
    (0, 2, 4),
    (0, 1, 12),
    (0, 4, 8),
    (5, 4, 7),
    (4, 3, 2),
    (3, 2, 5),
    (4, 1, 3),
    (1, 2, 6)
]
kruskal(G, 6)