T42 最小生成树 (MSL) 唯一的充分条件
T6_Kruskal_算法的数据结构
T6 Kruskal 算法的数据结构
Link to original
- 小根堆：用于存储图的所有边，按边权从小到大排序，方便每次取出最小边。
- 并查集：用于检测添加一条边是否会形成环路，支持快速合并和查找操作。
- 充分条件：图中所有边的权值均不相等
- 求 MST 的算法
- Kruskal 算法：按权值从小到大排序边，依次加入生成树，避免形成环。
- 适合稀疏图
- 可生成最小生成森林
- Prim 算法：从一个顶点开始，逐步扩展生成树，选择连接生成树与非生成树的最小权值边。
- 适合稠密图
- 只能处理单个连通分量
- Kruskal 算法：按权值从小到大排序边，依次加入生成树，避免形成环。