Kruskal算法 python

Kruskal算法是一种用于解决最小生成树问题的贪心算法。它通过逐步添加边来构建一棵树，保证每一步选择的边都是当前图中权值最小且不会形成环的一条边。以下是Python实现Kruskal算法的一个简单版本：

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    # 添加边到图中
    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    # 找到并返回所有顶点集合的排序
    def find(self, parent):
        if parent[self.V - 1] != self.V - 1:
            parent[self.V - 1] = self.find(parent)
        return parent[self.V - 1]

    # 合并两个集合
    def union(self, parent, rank, x, y):
        xroot = self.find(x)
        yroot = self.find(y)

        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1

    # Kruskal算法
    def kruskal_mst(self):
        result = []
        i, e = 0, 0
        self.graph = sorted(self.graph, key=lambda item: item[2])

        parent = list(range(self.V))
        rank = [0] * self.V

        while e < self.V - 1 and i < len(self.graph):
            u, v, w = self.graph[i]
            i += 1

            x = self.find(parent)
            y = self.find(rank)

            if x != y:
                e += 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        return result

# 示例用法
g = Graph(4)  # 假设我们有4个顶点
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)

print("Kruskal's MST:", g.kruskal_mst())