Kruskal算法
基本思想
Prim 算法是一个个更新点，而 Kruskal 算法是一个个更新边。
基本步骤
设 G = (V, E) 是连通网，用 T 来记录 G 上最小生成树边的集合。
- 从 G 中取最短边 e。如果边 e 所关联的两个顶点不在 T 的同一个连通分量中，则将该边加入 T。
- 从 G 中删除边 e。
- 重复步骤 1 和 2，直到 T 中有 n-1 条边。
算法要点
- Kruskal 算法每次选择权重最小的边，但只要该边会形成回路，就跳过它。
- 判断两个顶点是否在同一个连通分量中，可以使用**并查集（Union-Find）**数据结构来高效实现。
- 算法结束时，T 中包含 n-1 条边，构成一棵最小生成树。
链接到
- 上一个知识点：7.7 Prim算法
- 下一个知识点：7.9 拓扑排序