auto_ai 知识库

Appearance

最小生成树（Minimum Spanning Tree, MST）是在带权无向连通图中，选取 n-1 条边连接所有 n 个顶点，且总权值最小的生成树。经典算法有 Prim（从顶点出发扩展）和 Kruskal（从边出发排序选取），两者均基于贪心思想。

定义与核心原理 ​

生成树的性质 ​

  • 包含图中所有 n 个顶点
  • 恰好有 n-1 条边
  • 无环（树的定义）
  • 最小生成树：所有生成树中总权值最小的那棵

两种经典算法对比 ​

维度Prim 算法Kruskal 算法
出发点顶点（从一个点开始扩展）边（将所有边排序后依次选取）
数据结构邻接矩阵/邻接表 + 最小堆并查集（Union-Find）
适用场景稠密图（边多）稀疏图（边少）
时间复杂度O(n²) 或 O(E log n)O(E log E)（排序为主）

操作步骤 ​

Prim 算法 ​

1. 任选一个顶点加入生成树集合 S
2. 重复 n-1 次：
   a. 找到连接 S 和 V\S 的最小权值边
   b. 将该边的另一端顶点加入 S
3. 所有顶点都在 S 中，完成

Kruskal 算法 ​

1. 将所有边按权值从小到大排序
2. 初始化并查集，每个顶点独立成集合
3. 按权值从小到大遍历每条边：
   a. 如果边的两个端点不在同一集合 → 选取该边，合并集合
   b. 如果已在同一集合 → 跳过（会形成环）
4. 选取了 n-1 条边后完成

Prim 算法完整示例 ​

以 7 个顶点（V1~V7）的带权图为例，从 V1 出发：

边权值：V1-V2=2, V1-V3=4, V1-V4=1, V2-V4=3, V2-V5=10,
        V3-V4=2, V3-V6=5, V4-V5=7, V4-V6=8, V4-V7=4,
        V5-V7=6, V6-V7=1

执行步骤：

步骤已选顶点 S选取边权值说明
1{V1}V1-V41从V1出发的最小边
2{V1,V4}V6-V71跨S边界的最小边（V7在外部）
3{V1,V4,V7,V6}V1-V22跨边界最小边
4{V1,V2,V4,V6,V7}V3-V42跨边界最小边
5{V1,V2,V3,V4,V6,V7}V4-V7已选, V5最小=V4-V7→V5-V7=66最后连接V5

最终生成树：V1-V4(1) + V6-V7(1) + V1-V2(2) + V3-V4(2) + V5-V7(6) = 总权值 12

注：Prim 算法每一步选取连接"已选集合"和"未选集合"的最小权值边，与从哪个顶点出发无关，最终总权值唯一。

复杂度分析 ​

算法时间复杂度空间复杂度适用图
Prim（朴素）O(n²)O(n)稠密图
Prim（堆优化）O(E log n)O(n+E)各种图
KruskalO(E log E)O(E)稀疏图

实践应用 ​

  • 网络设计：计算机网络、通信网络的最小成本布线
  • 聚类分析：层次聚类中的单链接方法
  • 图像分割：基于图的图像分割算法
  • 近似算法：TSP 问题的 2-近似算法基于 MST

常见误区 ​

  1. 图不连通：最小生成树只存在于连通图中，非连通图只有"最小生成森林"
  2. Prim 和 Kruskal 选错：稠密图用 Prim（O(n²) 更优），稀疏图用 Kruskal（排序快）
  3. Kruskal 忘记判环：必须用并查集判断两个端点是否已连通，否则会形成环
  4. 边权相同：存在多个最小生成树，但总权值一定相同

一句话总结 ​

最小生成树是 n 个顶点取 n-1 条边、总权值最小的树：稠密图用 Prim（O(n²)），稀疏图用 Kruskal（O(E log E) + 并查集判环），总权值唯一。

相关概念 ​