Kruskal算法求解最小生成树问题

题目描述：
给定一个带权无向连通图，使用Kruskal算法找到该图的最小生成树。最小生成树是原图的一个子图，包含所有顶点但只有足够形成树的边，且所有边的权重之和最小。

解题过程：

1. 算法思想
   Kruskal算法采用贪心策略，每次选择权重最小的边加入生成树，但要确保不形成环。算法维护一个边的集合，初始时为空，最终形成最小生成树。

2. 数据结构准备

• 边集数组：将所有边按权重从小到大排序
• 并查集：用于检测是否形成环，记录顶点的连通分量

3. 详细步骤
   步骤1：创建所有边的列表，并按权重升序排序
   步骤2：初始化并查集，每个顶点自成一个集合
   步骤3：按权重从小到大遍历每条边：
   a. 检查当前边的两个顶点是否属于同一集合
   b. 如果属于不同集合，说明加入该边不会形成环：
   - 将该边加入最小生成树
   - 合并这两个顶点所在的集合
   c. 如果属于同一集合，跳过该边（避免形成环）
   步骤4：当生成树包含n-1条边时（n为顶点数），算法结束

4. 关键点说明

• 环检测：通过并查集快速判断两个顶点是否连通
• 贪心选择：每次选择当前最小权重的有效边
• 终止条件：生成树边数达到n-1时立即终止

5. 时间复杂度分析

• 边排序：O(E log E)
• 并查集操作：近似O(α(V))，其中α为反阿克曼函数
• 总复杂度：O(E log E + E α(V)) ≈ O(E log E)

6. 示例演示
   考虑一个4顶点图，边权重：
   AB=1, AC=4, AD=3, BC=2, BD=5, CD=6
   执行过程：
7. 选择AB(1)
8. 选择BC(2)
9. 选择AD(3) - 此时已连接所有顶点，生成树完成

这个算法保证找到全局最优解，因为每次选择的局部最优边最终能组成全局最优解。