编辑“︁Kruskal算法”︁（章节）

== 代码实现 ==

以下是Kruskal算法的Python实现示例，使用并查集来管理连通分量：

<syntaxhighlight lang="python">
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    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:
            return False  # 已在同一连通分量
        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_x] = root_y
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_y] += 1
        return True

def kruskal(vertices, edges):
    edges.sort(key=lambda x: x[2])  # 按权重排序
    uf = UnionFind(vertices)
    mst = []
    for u, v, weight in edges:
        if uf.union(u, v):
            mst.append((u, v, weight))
            if len(mst) == vertices - 1:
                break
    return mst

# 示例输入
vertices = 4
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

# 执行Kruskal算法
mst = kruskal(vertices, edges)
print("最小生成树的边：")
for u, v, weight in mst:
    print(f"{u} -- {v} : {weight}")
</syntaxhighlight>

'''输出：'''
<pre>
最小生成树的边：
2 -- 3 : 4
0 -- 3 : 5
0 -- 1 : 10
</pre>