xxx 最小生成树的 Kruskal 算法

题目描述
给定一个连通无向图 \(G = (V, E)\)，其中每条边 \(e \in E\) 具有权重 \(w(e)\)，要求找到总权重最小的生成树（即最小生成树，MST）。Kruskal 算法通过贪心策略，按边权重升序逐步选择边，并避免形成环，最终构造出最小生成树。

解题过程

步骤 1：算法核心思想
Kruskal 算法的核心是贪心选择：

1. 将所有边按权重从小到大排序。
2. 按顺序检查每条边，若加入当前边不会在已选边集合中形成环，则将其加入最小生成树；否则跳过。
3. 重复直到选中 \(|V| - 1\) 条边（生成树的边数恒为顶点数减一）。

关键点：需高效判断加入边是否形成环，可通过并查集（Union-Find）数据结构实现。

步骤 2：数据结构准备

1. 边排序：使用优先队列（或简单排序）按权重升序存储边。
2. 并查集（Union-Find）：
   • 初始化每个顶点为独立的集合（父节点指向自己，秩为 0）。
   • Find(u)：查找顶点 \(u\) 所在集合的根节点（带路径压缩优化）。
   • Union(u, v)：合并两个顶点所在的集合（按秩合并优化）。

步骤 3：逐步执行过程
以具体例子说明：

顶点：{A, B, C, D}
边及权重：AB(1), AC(3), AD(4), BC(2), BD(5), CD(6)

1. 初始化：

   • 边按权重排序：[AB(1), BC(2), AC(3), AD(4), BD(5), CD(6)]
   • 并查集：每个顶点独立集合 {A}, {B}, {C}, {D}
   • 最小生成树边集 \(T = \emptyset\)，计数器 \(count = 0\)。

2. 处理边 AB(1)：

   • Find(A) ≠ Find(B)（不同集合），执行 Union(A, B)。
   • 加入 \(T\)：{AB}，\(count = 1\)。
   • 集合变为 {A,B}, {C}, {D}。

3. 处理边 BC(2)：

   • Find(B) ≠ Find(C)，执行 Union(B, C)。
   • 加入 \(T\)：{AB, BC}，\(count = 2\)。
   • 集合变为 {A,B,C}, {D}。

4. 处理边 AC(3)：

   • Find(A) = Find(C)（同属 {A,B,C}），跳过（避免环）。

5. 处理边 AD(4)：

   • Find(A) ≠ Find(D)，执行 Union(A, D)。
   • 加入 \(T\)：{AB, BC, AD}，\(count = 3 = |V| - 1\)，算法终止。

结果：最小生成树总权重 = 1 + 2 + 4 = 7，边集为 {AB, BC, AD}。

步骤 4：关键优化与复杂度分析

1. 并查集优化：
   • 路径压缩与按秩合并使每次 Find 和 Union 操作接近常数时间 \(O(\alpha(|V|))\)。
2. 时间复杂度：
   • 边排序：\(O(|E| \log |E|)\)。
   • 并查集操作：\(O(|E| \cdot \alpha(|V|))\)。
   • 总体：\(O(|E| \log |E|)\)，适用于稀疏图（边数较少）。

步骤 5：正确性证明（简要）

• 安全边选择：Kruskal 每次选择的边是当前连接两个不同组件的最小权重边，符合 MST 的割性质（Cut Property）。
• 无环性：通过并查集显式避免环的形成。
• 生成树性质：最终边数恰为 \(|V| - 1\)，且连通所有顶点。