克鲁迪斯卡尔最小生成树

克鲁斯卡尔算法是一种用于求解图的最小生成树的算法。它基于贪心策略，通过不断选择权值最小的边来构建最小生成树。下面是克鲁斯卡尔算法的步骤：

1. 将图中的所有边按照权值从小到大进行排序。
2. 创建一个空的集合，用于存放最小生成树的边。
3. 遍历排序后的边集合，依次选择权值最小的边。
4. 如果选择的边不会导致形成环路，则将该边加入最小生成树的边集合中。
5. 重复步骤4，直到最小生成树的边数等于图的顶点数减1，或者遍历完所有的边。

以下是一个示例代码，演示了如何使用克鲁斯卡尔算法求解最小生成树：

class MFSet:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n

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

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        elif self.rank[x_root] > self.rank[y_root]:
            self.parent[y_root] = x_root
        else:
            self.parent[y_root] = x_root
            self.rank[x_root] += 1

def kruskal(graph):
    edges = []
    for u in range(len(graph)):
        for v in range(u + 1, len(graph)):
            if graph[u][v] != 0:
                edges.append((u, v, graph[u][v]))
    edges.sort(key=lambda x: x[2])

    m = len(graph)
    mfset = MFSet(m)
    result = []

    for edge in edges:
        u, v, weight = edge
        if mfset.find(u) != mfset.find(v):
            mfset.union(u, v)
            result.append(edge)

    return result

# 示例图的邻接矩阵表示
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]

minimum_spanning_tree = kruskal(graph)

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

这段代码演示了如何使用克鲁斯卡尔算法求解给定图的最小生成树。首先，我们定义了一个MFSet类来表示构造生成树过程中的连通分量。然后，我们使用克鲁斯卡尔算法对图的边进行排序，并依次选择权值最小的边加入最小生成树的边集合中。最后，我们输出生成树中的各条边以及它们的权值。