Kruskal算法[编辑 | 编辑源代码]

Kruskal算法是一种用于求解最小生成树（Minimum Spanning Tree, MST）问题的贪心算法。由约瑟夫·克鲁斯卡尔（Joseph Kruskal）于1956年提出，该算法通过逐步选择图中权重最小的边来构建最小生成树，同时确保不形成环路。Kruskal算法适用于稀疏图，其时间复杂度主要取决于边的排序操作，通常为 $O (E \log E)$ ，其中 $E$ 为边的数量。

算法原理[编辑 | 编辑源代码]

Kruskal算法的核心思想是：

将图中的所有边按权重从小到大排序。
从权重最小的边开始，依次选择边加入生成树中，若该边的两个顶点不在同一连通分量中（即不形成环路），则将该边加入生成树。
重复上述过程，直到生成树中包含 $V - 1$ 条边（ $V$ 为顶点数）。

该算法使用并查集（Disjoint Set Union, DSU）数据结构来高效地判断两个顶点是否属于同一连通分量。

代码实现[编辑 | 编辑源代码]

以下是Kruskal算法的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}")

输出：

最小生成树的边：
2 -- 3 : 4
0 -- 3 : 5
0 -- 1 : 10

1. 按边权重排序： $(2, 3, 4), (0, 3, 5), (0, 2, 6), (0, 1, 10), (1, 3, 15)$ 。 2. 选择 $(2, 3, 4)$ ，加入生成树。 3. 选择 $(0, 3, 5)$ ，加入生成树。 4. 选择 $(0, 2, 6)$ ，但会形成环路（0-3-2-0），跳过。 5. 选择 $(0, 1, 10)$ ，加入生成树。 6. 生成树已包含 $3$ 条边（ $4 - 1 = 3$ ），算法结束。

最终的最小生成树总权重为 $4 + 5 + 10 = 19$ 。

时间复杂度[编辑 | 编辑源代码]

Kruskal算法的时间复杂度主要由以下两部分决定： 1. 排序边： $O (E \log E)$ 。 2. 并查集操作：每次查找和合并操作的平均时间复杂度为 $O (α (V))$ ，其中 $α$ 为反阿克曼函数，近乎常数。因此，总时间复杂度为 $O (E \log E)$ 。

实际应用[编辑 | 编辑源代码]

Kruskal算法在以下场景中有广泛应用： 1. 网络设计：如设计通信网络或电力网络，以最小化布线成本。 2. 交通规划：规划道路或铁路，确保所有城市连通且总建设成本最低。 3. 聚类分析：在机器学习中用于层次聚类。

与其他算法的比较[编辑 | 编辑源代码]

Prim算法：同样用于求解最小生成树，但基于顶点扩展，适合稠密图。
Borůvka算法：另一种贪心算法，适用于并行计算。

Kruskal算法的优势在于实现简单且易于理解，尤其适合稀疏图。

总结[编辑 | 编辑源代码]

Kruskal算法是一种高效且直观的最小生成树算法，通过贪心策略和并查集数据结构的结合，能够快速求解连通图的最小生成树问题。初学者可以通过理解其核心思想和实现细节，掌握贪心算法在图论中的应用。

Kruskal算法