切割定理（Cut Property）#

设 S 为图 G 中任意一个顶点子集，在所有连接 S 内顶点与 S 外顶点的边中，权值最小的一条一定属于某棵 MST。这是 Prim 和 Kruskal 算法的理论基础。

核心思想#

从一个顶点出发，每次将离当前生成树最近的顶点加入树中，逐步扩展。

• 贪心策略：每一步选择连接树内顶点与树外顶点的权值最小的边
• 逐顶点生长：每次加入一个顶点，共执行 n-1 轮
• 辅助数组：lowcost[] 记录树外各顶点到树的最短距离，closest[] 记录对应的树内顶点

算法过程#

1. 初始化：选取起始顶点加入 U，用邻接矩阵初始化 lowcost[] 和 closest[]
2. 循环 n-1 次：
   • 在 lowcost[] 中找到值最小且未加入树的顶点 k
   • 将 k 加入 U（标记 lowcost[k] = 0）
   • 扫描 k 的所有邻接顶点 j，若 cost[k][j] < lowcost[j]，则更新 lowcost[j] 和 closest[j]

复杂度分析#

核心思想#

把所有边按权值从小到大排序，依次选取，只要不形成回路就保留。当选够 n-1 条边时算法结束。

• 按边贪心：对所有边按权值升序排序，依次选取最小权值边
• 并查集判环：若边的两个端点已属于同一连通分量，则加入该边会形成回路，跳过
• 选够 n-1 条边时结束

算法过程#

1. 将图中所有边按权值升序排序
2. 初始化并查集，每个顶点各自为一个独立集合
3. 依次遍历排序后的边 (u, v, w)：
   • 若 u 和 v 不在同一集合，选中该边，合并两个集合
   • 若 u 和 v 在同一集合，跳过该边
4. 当选中的边数达到 n-1 时，MST 构建完成

并查集在 Kruskal 中的作用#

并查集（Union-Find）是 Kruskal 算法高效判环的关键数据结构：

若边 (u, v) 的两个端点已在同一集合中，说明 u 到 v 之间已存在路径，再加入该边必然形成回路。

复杂度分析#