Алгоритм Крускала используется для поиска минимального остовного дерева (МОД) в связном взвешенном графе. Вот пример его реализации на Python:

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])
        return self.parent[p]

    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP != rootQ:
            if self.rank[rootP] > self.rank[rootQ]:
                self.parent[rootQ] = rootP
            elif self.rank[rootP] < self.rank[rootQ]:
                self.parent[rootP] = rootQ
            else:
                self.parent[rootQ] = rootP
                self.rank[rootP] += 1

def kruskal(graph):
    edges = []
    for u in graph:
        for v, weight in graph[u]:
            edges.append((weight, u, v))
    
    # Sort edges by weight
    edges.sort()
    
    uf = UnionFind(len(graph))
    mst = []
    
    for weight, u, v in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
    
    return mst

# Example usage
graph = {
    0: [(1, 4), (2, 3)],
    1: [(0, 4), (2, 1), (3, 2)],
    2: [(0, 3), (1, 1), (3, 4)],
    3: [(1, 2), (2, 4)]
}

mst = kruskal(graph)
print("Minimum Spanning Tree:", mst)

Этот код включает в себя класс `UnionFind` для эффективного управления множеством disjoint-sets и функцию `kruskal`, которая принимает на вход граф в виде словаря, где ключи — вершины, а значения — списки смежности с весами ребер. Алгоритм Крускала возвращает минимальное остовное дерево в виде списка рёбер.