用python实现Kruskal算法求最小生成树

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, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

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

        # 如果根节点相等，说明它们已经是同一集合，不需要合并
        if xroot == yroot:
            return

        # 否则，将较小集合的根添加到较大集合的根下
        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(graph):
    result = []  # 最小生成树
    i, e = 0, 0  # 边的数量
    graph.sort(key=lambda item: item[2])  # 按权重从小到大排序

    V = len(graph)  # 顶点数
    parent = list(range(V))  # 创建每个顶点的父节点，初始化为它自身
    rank = [0] * V  # 初始秩为0，防止形成环

    while i < V - 1:  # 当添加V-1条边时得到生成树
        u, v, w = graph[i]
        x = self.find(parent, u)
        y = self.find(parent, v)

        # 如果两个顶点不在同一集合中
        if x != y:
            e += 1
            result.append([u, v, w])
            self.union(parent, rank, x, y)
        i += 1

    print("Minimum Spanning Tree:")
    for edge in result:
        print(f"Edge: {edge[0]} - {edge[1]}, Weight: {edge[2]}")

# 示例：
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)

kruskal_mst(g)