KAN`ский блог Мысли вслух…
  • Июн
    18

    Реализация Алгоритма Крускала на python

    Алгоритм Крускала используется для поиска минимального остовного дерева (МОД) в связном взвешенном графе. Вот пример его реализации на 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`, которая принимает на вход граф в виде словаря, где ключи — вершины, а значения — списки смежности с весами ребер. Алгоритм Крускала возвращает минимальное остовное дерево в виде списка рёбер.

    No Comments

Comments are closed.