kruskal算法求最小生成树

Kruskal算法是一种贪心算法，用于求解最小生成树问题。其基本思想是将所有边按照权值从小到大排序，然后依次加入到生成树中，如果加入该边不会形成环，则将该边加入生成树中，否则舍弃该边。直到生成树中有n-1条边为止，其中n为图中节点的个数。

以下是Kruskal算法求解最小生成树的Python代码示例：

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

# 定义并查集类
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.count = 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):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_x] = root_y
            self.count -= 1

# 定义Kruskal算法函数
def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda x: x.w)
    res = []
    for e in edges:
        if uf.count == 1:
            break
        if uf.find(e.u) != uf.find(e.v):
            uf.union(e.u, e.v)
            res.append(e)
    return res

# 示例
edges = [Edge(0, 1, 4), Edge(0, 2, 3), Edge(1, 2, 1), Edge(1, 3, 2), Edge(2, 3, 5)]
res = kruskal(4, edges)
for e in res:
    print(e.u, e.v, e.w)

输出结果为：

1 2 1
1 3 2
0 2 3