1 算法原理及步骤
Kruskal’s 算法用于寻找无向图的最小生成树。它通过逐步选择最小权重的边，确保在不形成环的情况下连接所有节点。
原理
- 贪心策略：从权重最小的边开始选择，逐步构建生成树。
- 避免环路：使用并查集（Union-Find）数据结构来检测并避免环路。
实现步骤
（1）初始化：
- 将每个节点作为一个独立的集合。
- 创建空的最小生成树集合。
（2）边排序：
- 将图中的所有边按权重升序排序。
（3）选择边：
- 依次选择排序后的边。
- 使用并查集判断边的两个端点是否属于不同的集合。
- 如果不在同一集合，选择该边并合并集合。
（4）重复过程：
- 重复选择和合并操作，直到生成树包含所有节点（n-1条边）。