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

= Kruskal算法 =

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

== 算法原理 ==

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

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

== 算法步骤 ==

以下是Kruskal算法的详细步骤：
1. '''初始化'''：将每个顶点视为一个独立的连通分量。
2. '''排序边'''：将所有边按权重升序排列。
3. '''遍历边'''：按顺序检查每条边：
   - 如果边的两个顶点属于不同的连通分量，则将该边加入生成树，并合并这两个连通分量。
   - 否则，跳过该边以避免形成环路。
4. '''终止条件'''：当生成树中包含<math>V-1</math>条边时，算法结束。

== 代码实现 ==

以下是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>

== 示例分析 ==

以下是一个图的示例，展示Kruskal算法的执行过程：

<mermaid>
graph LR
    A((0)) -- 10 --- B((1))
    A -- 6 --- C((2))
    A -- 5 --- D((3))
    B -- 15 --- D
    C -- 4 --- D
</mermaid>

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

最终的最小生成树总权重为<math>4 + 5 + 10 = 19</math>。

== 时间复杂度 ==

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

== 实际应用 ==

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

== 与其他算法的比较 ==

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

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

== 总结 ==

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:图论算法]]