实现Kruskal算法实验

Kruskal算法是一种用于生成最小生成树的贪心算法。最小生成树是一种包含所有节点但是权重之和最小的树。下面是一个使用Kruskal算法实现最小生成树的Python代码示例：

# 定义边的类
class Edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

# 定义Kruskal算法
def kruskal(n, edges):
    # 初始化并查集
    parent = [i for i in range(n)]
    rank = [0] * n

    # 边按权重从小到大排序
    edges.sort(key=lambda x: x.w)

    # 初始化最小生成树的权重和
    mst_weight = 0

    # 遍历每条边
    for e in edges:
        # 判断两个端点是否在同一个集合中
        p1 = find(parent, e.u)
        p2 = find(parent, e.v)

        # 如果不在同一个集合中，则将它们合并，并将该边加入最小生成树
        if p1 != p2:
            union(parent, rank, p1, p2)
            mst_weight += e.w

    return mst_weight

# 定义并查集的find和union操作
def find(parent, i):
    if parent[i] != i:
        parent[i] = find(parent, parent[i])
    return parent[i]

def union(parent, rank, x, y):
    xroot = find(parent, x)
    yroot = find(parent, y)

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

# 测试代码
n = 5
edges = [Edge(0, 1, 2), Edge(0, 3, 6), Edge(1, 2, 3), Edge(1, 3, 8),
         Edge(1, 4, 5), Edge(2, 4, 7), Edge(3, 4, 9)]

mst_weight = kruskal(n, edges)
print("最小生成树的权重和为：", mst_weight)

这个代码示例中，我们使用了一个边的类来表示每条边，包含它的两个端点和它的权重。然后我们定义了Kruskal算法和并查集的find和union操作。最后，我们测试了这个算法，生成了一个包含5个节点的图，并计算了它的最小生成树的权重和。