数据结构基础：最小生成树高效连通图的奥秘

1、什么是最小生成树？

在深入“最小生成树”之前，先回顾一下之前的几个概念。

1.1、图

在数据结构中，图用于表示“多对多”的关系。它由两部分组成：

• 顶点 ： 表示事物，比如城市、交叉路口、网络中的计算机。
• 边 ： 表示事物之间的连接，比如城市间的公路、路口间的街道、计算机间的网线。

本文我们主要讨论 带权无向图 ：

• 无向 ： 边是没有方向的。从A到B和从B到A是同一条路。
• 带权： 每条边都有一个“权重”或“成本”，比如公路的长度、网线的铺设费用。

1.2、树

树是一种特殊的图。它满足两个核心条件：

一个有 N 个顶点的树，它必定有且仅有 N-1 条边。

1.3、生成树

给定一个连通图 G，它的 生成树是 G 的一个子图（即只包含G中的部分边和所有顶点），并且这个子图本身是一棵树。

换句话说，生成树就是图G的一个“骨架”，它刚好用 最少的边 (N-1条) 把 G 中 所有的顶点 都连通起来。

(注意：一个图可以有很多棵生成树。例如上图，“生成树 1” 和 “生成树 2” 都是有效的生成树，因为它们都用 3 (N-1) 条边连接了所有 4 (N) 个顶点，并且没有环路。)

1.4、最小生成树

现在我们把“带权图”和“生成树”结合起来。

一个带权连通图 G，它可能有很多棵不同的生成树。每棵生成树的所有边权加起来，会得到一个总权重。

最小生成树 (Minimum Spanning Tree, MST) 就是指在所有可能的生成树中，总权重（总成本）最小的那一棵。

MST 有什么用？

MST 非常有用！它的核心思想是 用最小的成本连接所有节点。比如：

• 电信/网络： 要铺设光缆连接n个城市，如何铺设才能使光缆总长度最短？
• 交通： 要修建公路网连接所有村庄，如何设计才能使总造价最低？
• 电路设计： 要在电路板上连接n个引脚，如何走线才能使总铜线用量最少？

2、MST的核心性质

最小生成树不仅仅是一个概念，它具有一些非常强大且优美的数学性质。正是这些性质，才使得我们能够设计出高效的贪心算法来找到它。

2.1、性质一：N-1条边与无环

这是一个“树”的基本性质。对于一个包含 N 个顶点的图，它的一棵生成树（包括最小生成树）必定 包含且仅包含 N-1 条边，并且 绝对没有环路。

• 下限：连通n个顶点至少需要n-1条边
• 上限：n条或更多边必然形成环（不再是树）
• 结论：既要连通又要无环 → 恰好n-1条边

直观理解：第一个顶点不需要边，之后每新增一个顶点，用一条边连到已有的树上。n个顶点需要n-1次连接。

2.2、性质二：唯一权重

一个图的最小生成树 可能不唯一（如果存在多条权重相同的边）。但是，所有这些不同的最小生成树，它们的 总权重 必定是 相同且唯一 的。

2.2.1、为什么 MST 的 结构 可能 不唯一？

一个图的最小生成树 可能不唯一。 这种情况 当且仅当 图中存在多条权重相同的边，并且在构建MST的过程中，算法（无论是Prim还是Kruskal）遇到了一个“岔路口”，即有多条相同权重的“最优解”可供选择。

例如，在Kruskal算法中，如果排序后有两条权重同为 w 的边 e1 和 e2，并且在某一步，选择 e1 或 e2 都是“安全”（不形成环路）的，那么就可能产生两条不同的MST路径。

上图中，Kruskal算法会先选择 A-C (1) 和 B-D (1)。接下来，它需要再选一条权重为2的边。此时，选 A-B (2) 或 C-D (2) 都可以，都会得到一个总权重为4的MST。因此，MST的结构不唯一。

2.2.2、为什么 MST 的 总权重 必定 唯一？

这可以通过一个简单的反证法(Proof by Contradiction)来理解。

假设一个图G的最小生成树的 总权重不唯一。

这意味着存在至少两个 总权重不同 的生成树T1 和 T2，它们 都是 最小生成树。

• 设 T1 的总权重为 W1。
• 设 T2 的总权重为 W2。
• 并且我们假设 W1≠W2，不妨设 W1<W2。

这里就出现了根本性的矛盾：

根据“最小生成树”的定义，它必须是所有生成树中总权重 最小 的那一棵。

• 如果 T2 (总重 W2) 是一棵最小生成树，那么W2 必须是最小的总权重。
• 但是我们假设存在另一棵生成树 T1，其总重 W1<W2。
• 这说明 W2 并不是最小的总权重（因为存在一个更小的 W1），所以 T2 根本不可能是 最小生成树。

这与我们的前提“T2 是一棵最小生成树”相矛盾。因此，我们最初的假设“总权重不唯一”是 错误 的。

结论： 一个图的所有最小生成树（无论有多少种不同的结构），它们都必须共享 同一个、唯一 的 最小总权重。

2.3、切割属性

:::info 切割定理：将图的所有顶点分成两个不相交的集合 和 （这被称为一个“切割”）。如果一条边 是所有横跨这个切割（即一个顶点在 中，另一个在 中）的边中权重最小的那条，那么 必定属于图的某个最小生成树。

:::

这是所有MST算法的理论基石：

“切割”这个词听起来很专业，但它的意思非常简单：就是“分两组”。想象一下，你把一个图 G 中 所有 顶点（V）分成 两个 互不相交的集合（两堆）。

• 集合 S： 我们可以称之为“我们已占领的领土”（比如 Prim 算法中已访问的节点）。
• 集合 V-S： 称之为“尚未探索的区域”（未访问的节点）。

这个“一刀切”的划分动作，就叫做一次“切割”。

8 TE.MIN(3)(最轻跨越边) TE.OTHER(6)(另一条跨越边) –>

• 集合 S (蓝色组)： 我们任选 {A, C, E}
• 集合 V-S (灰色组)： 剩下所有节点 {B, D, F}
• 跨越切割的边 ： (A-B, 4), (C-B, 5), (C-D, 3), (D-E, 4), (E-F, 6)。
• 切割属性： 在所有这些“跨越边”中，权重 最小 的那一条，即 (C-D, 权重3)，必定 属于图的最小生成树 (MST)。

切割定理的证明

我们可以用反证法来理解：

Prim 算法正是切割属性的完美应用：它始终维护一个集合 S（已访问的点），每次都贪心地选择连接 S 和 V-S 的“最轻跨越边”，并将其加入MST。

2.4、环路属性

这个性质与切割属性互为补充：

回路性质：在一个图中，对于任意一个环，环上权重最大的那条边 $ e $ 必定不属于任何一个最小生成树。（前提是所有边的权重是唯一的，如果权重可以相同，则它“可能不属于”）。

环路属性的证明

我们同样可以用反证法来理解：

这正是Kruskal算法的核心原理：Kruskal算法按权重从小到大添加边。当它遇到一条新边 ，如果 find(u) == find(v)，这意味着

u

u

u 和

v

v

v 已经连通了，加入

(

u

,

v

)

(u, v)

(u,v)必定会形成一个环。由于

(

u

,

v

)

(u, v)

(u,v)是这个环中最后被检查的边（因此也是权重最大的边），根据回路性质，Kruskal算法会安全地丢弃这条边。

3、核心思想

寻找MST的算法都基于一种 贪心策略。贪心，就是“目光短浅”，只顾眼前利益。

在MST问题中，贪心就是：“每次都选择当前看起来最好（权重最小）的边”。

你可能会问：为什么这种“短视”的行为能保证最后得到的是“全局最优”（总权重最小）呢？万一我为了贪图眼前的便宜，导致后面必须选一条特别贵的边呢？

好这正是因为MST问题满足我们上一节讨论的 “切割属性” 和 “环路属性”。

这两大属性就像“尚方宝剑”，保证了我们“贪心”地做出的每一步局部最优选择（选最轻的跨越边，或丢弃最重的环路边），也必定是通往“全局最优”（总权重最小）的正确一步。

两大经典算法 Prim 和 Kruskal，就是基于这两大属性演化而来的。

4、算法一：Prim (普里姆) 算法

Prim 算法是一种“加点法”，它的贪心策略非常直观。

Prim 算法是切割定理的直接应用。它的思想是“从一个点开始，不断生长，直到覆盖所有点”。

• 比喻：想象你在一片黑暗中点亮了一盏灯（起始顶点）。这盏灯照亮了它周围的路（与它相连的边）。你选择一条最短的路（权重最小的边）走到下一个路灯并点亮它。现在两盏灯一起照亮了更多的路… 重复这个过程，直到所有路灯都被点亮。
• 算法步骤：
  • 1. 任选一个顶点作为起始点，将其加入“已访问”集合 $S$
  • 2. 找到所有横跨切割 $(S,V-S)$
  • 3. 选择其中权重最小的那条边 $(u,v)$
  • 4. 将这条边加入MST，并将顶点 $v$
  • 5. 重复步骤 2-4，直到所有顶点都加入 $S$

4.1、Prim算法的正确性

Prim 算法每一步都只选“当前最短”的边，这种“短视”的贪心行为，怎么能保证最后得到的“总和”是最小的呢？

答案在于“性质三：切割属性 ”

Prim 算法的每一步，都是“切割属性”的一次完美应用：

• “切割”在哪里？ Prim 算法在每一步都自动地制造了一个“切割”：
  • 集合 S = 所有“已占领”的蓝色顶点。
  • 集合 V-S = 所有“未占领”的灰色顶点。
• “跨越切割的边”在哪里？ 就是我们存放在“最小堆” 里的所有“候选边”（连接一个蓝色点和一个灰色点的边）。
• Prim 的贪心选择： Prim 算法从“最小堆”中取出权重最小的那条边。这等价于：“在所有跨越切割的边中，找到了权重最小的那一条”。
• “切割属性”的保证： 切割属性告诉我们：“任何跨越切割的最轻边，必定属于最小生成树”。

结论： Prim 算法每一步贪心选出的“最短候选边”，都必定是 MST 的一部分。因此，它的每一步都是“安全”且“正确”的。把这些“正确”的局部选择拼在一起，最终得到的自然就是全局最优的最小生成树。

4.2、Prim算法的效率

Prim 算法的关键在于“如何快速找到那条权重最小的跨越边”？

4.2.1、朴素实现

这种实现方式非常直观，它利用数组来跟踪“未访问顶点”到“已访问集合 ”的最短距离。

核心数据结构：

• visited[V]：一个布尔数组，visited[i] = true 表示顶点 $i$
• dist[V]：一个整数数组，dist[v] 存储的是顶点 (必须是未访问的) 连接到任意一个已访问顶点的最短边的权重。

算法流程：

为什么是

O

(

V

2

)

O(V^2)

O(V2) ？

• 外层循环 (第2步) 确定了要执行$V$
• 在每次循环中，步骤 (a) “找到未访问的最小 dist 顶点” 必须遍历整个 dist 数组，这个操作是$O(V)$
• 步骤 (d) “更新邻居” 在使用邻接矩阵时也是 。
• 总复杂度 = $V\times (O(V)\text{ [找最小]}+O(V)\text{ [更新]})=O(V^2)$

演示 (朴素实现):

假设我们有图 (A, B, C, D)，从 A 开始。

4.2.2、堆实现

这种实现是为了优化朴素实现中的 “查找最小”这一瓶颈。

核心数据结构：

• visited[V]：一个布尔数组或集合，作用相同。
• PriorityQueue (min-heap)：一个最小优先队列（最小堆）。
  • 关键： 堆里存储的不再是顶点，而是边！
• 存储格式：(weight, vertex_u, vertex_v)，其中 u 是已访问顶点，v 是未访问顶点。堆会根据 weight 自动排序。

算法流程：

为什么是

O

(

E

log

⁡

V

)

O(E \\log V)

O(ElogV)？

• 总共有 $O(V)$
• 在优化的实现中，堆的大小最多为 $O(V)$
• 无论是 $O(E\log E)$

演示 (堆实现):

4.2.3、实现对比

4.3、可视化演示

https://code.juejin.cn/pen/7571017462003548210?embed=true

4.4、代码实现

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import heapq

def prim(graph, start_node):
# graph 是一个邻接表, 格式: { 'A': [ (权重, 'B'), (权重, 'C') ], … }
mst = [] # 存储最小生成树的边 (权重, u, v)
visited = set([start_node]) # 已访问的顶点集合 (S)

# 优先队列 (min-heap) 存储 "候选边" (权重, u, v)
# u 是已访问顶点, v 是未访问顶点
candidate_edges = []

# 将起始节点的所有边加入优先队列
for weight, neighbor in graph[start_node]:
heapq.heappush(candidate_edges, (weight, start_node, neighbor))

total_weight = 0

# 当 MST 的边数达到 V-1 时停止 (这里用优先队列是否为空判断更简单)
while candidate_edges:
# 1. 弹出当前权重最小的横跨边
weight, u, v = heapq.heappop(candidate_edges)

# 2. 检查 v 是否已访问，如果已访问，说明 (u,v) 都在 S 中，形成环，跳过
if v in visited:
continue

# 3. 接受这条边：v 加入 S, 边加入 MST
visited.add(v)
mst.append((weight, u, v))
total_weight += weight

# 4. 将 v 的所有新 "横跨边" 加入优先队列
for new_weight, new_neighbor in graph[v]:
if new_neighbor not in visited:
heapq.heappush(candidate_edges, (new_weight, v, new_neighbor))

return mst, total_weight

if __name__ == "__main__":
graph_adj = {
'A': [(4, 'B'), (2, 'C')],
'B': [(4, 'A'), (5, 'C'), (10, 'D')],
'C': [(2, 'A'), (5, 'B'), (3, 'D'), (8, 'E')],
'D': [(10, 'B'), (3, 'C'), (7, 'E'), (11, 'F')],
'E': [(8, 'C'), (7, 'D'), (1, 'F')],
'F': [(11, 'D'), (1, 'E')]
}

mst_edges, cost = prim(graph_adj, 'A')
print(f"Prim's MST: {mst_edges}")
print(f"Total Cost: {cost}")
# 运行追踪:
# 1. Start A. visited={A}. heap=[(2,A,C), (4,A,B)]
# 2. Pop (2,A,C). v=C. visited={A,C}. mst=[(2,A,C)].
# Push (5,C,B), (3,C,D), (8,C,E). heap=[(3,C,D), (4,A,B), (5,C,B), (8,C,E)]
# 3. Pop (3,C,D). v=D. visited={A,C,D}. mst=[(2,A,C), (3,C,D)].
# Push (10,D,B), (7,D,E), (11,D,F). heap=[(4,A,B), (5,C,B), (7,D,E), (8,C,E), (10,D,B), (11,D,F)]
# 4. Pop (4,A,B). v=B. visited={A,C,D,B}. mst=[(2,A,C), (3,C,D), (4,A,B)].
# Push (10,B,D). heap=[(5,C,B), (7,D,E), (8,C,E), (10,D,B), (10,B,D), (11,D,F)]
# 5. Pop (5,C,B). v=B. visited. Skip.
# 6. Pop (7,D,E). v=E. visited={A,C,D,B,E}. mst=[(2,A,C), (3,C,D), (4,A,B), (7,D,E)].
# Push (1,E,F). heap=[(1,E,F), (8,C,E), (10,D,B), (10,B,D), (11,D,F)]
# 7. Pop (1,E,F). v=F. visited={A,C,D,B,E,F}. mst=[(2,A,C), (3,C,D), (4,A,B), (7,D,E), (1,E,F)].
# F的邻居D,E均已访问.
# 8. Pop (8,C,E). v=E. visited. Skip.
# … (skip all)
# 最终结果: [(2, 'A', 'C'), (3, 'C', 'D'), (4, 'A', 'B'), (7, 'D', 'E'), (1, 'E', 'F')] -> Total: 17

5、算法二：Kruskal (克鲁斯卡尔) 算法

Kruskal 算法采用了另一种贪心策略。它的思想是“从森林开始，不断连接，直到汇聚成一棵树”。

• 比喻：想象图中的每个顶点都是一座独立的“岛屿”（一个森林）。你有一张按成本排序的“造桥”蓝图（所有边按权重排序）。你从成本最低的桥开始，依次考虑是否建造它。如果这座桥连接的是两座不同的岛屿，你就建造它（将岛屿合并）；如果它连接的是同一座岛屿的两个地方（形成环），你就放弃它。重复这个过程，直到所有岛屿都连通。
• 算法步骤：
  • 1. 创建一个“森林”，其中每个顶点都是一棵独立的树。
  • 2. 将图中所有的边放入一个集合，并按权重从小到大排序。
  • 3. 遍历排序后的边 $(u,v)$
  • 4. 检查 $u$
  • 5. 如果不在同一棵树中：将这条边加入MST，并合并$u$
  • 6. 如果在同一棵树中：跳过这条边（否则会形成环）。
  • 7. 重复步骤 3-6，直到MST中有 $V-1$

5.1、如何高效的检测环

在Kruskal算法的步骤4中，我们如何快速“检查

u

u

u和

v

v

v是否已在同一棵树中”？

如果用图的遍历（如DFS或BFS）来检查，每次检查都需要

O

(

V

+

E

)

O(V+E)

O(V+E)的时间，这太慢了。而这正是 并查集数据结构的完美应用场景。

并查集是一种专门用于管理“不相交集合”的数据结构，它提供两个核心操作：

• find(i): 查找元素 $i$
• union(i, j): 合并$i$

在Kruskal算法中，每个“集合”就代表一棵“树”或一个“连通分量”。

• 检查是否成环：if (find(u) == find(v))
• 合并两个分量：union(u, v)

并查集的工作原理 (带优化)

我们通常使用一个数组 parent[V] 来实现并查集。parent[i] 存储节点

i

i

i的父节点。如果 parent[i] == i，则

i

i

i是该集合的根节点。

1. 基础 Find (未优化)

find(i) 操作会不断向上查找，直到找到根节点。但这可能导致树退化成一条长链，使得 find 操作变为

O

(

V

)

O(V)

O(V)。

2. 优化一：路径压缩

为了避免长链，我们在“查找”的同时“压缩”路径。当 find(i) 被调用时，我们找到根节点 root 后，会把从$ i $ 到 root 路径上的所有节点都直接指向 root。这极大地扁平化了树的结构。

优化二：按大小 (或按秩) 合并

为了防止树长得太高，我们在 union(i, j) 时遵循一个规则：总是把较小的树（集合）合并到较大的树（集合）上。这能确保树的深度保持在$ O(\\log V) $级别。

通过这两种优化，并查集的 find 和 union 操作的平摊时间复杂度

O

(

α

(

V

)

)

O(\\alpha(V))

O(α(V))可以达到 ，其中

α

\\alpha

α是反阿克曼函数，它增长极其缓慢，在所有实际应用中都可以被看作是一个极小的常数（比如 4 或 5）。这使得并查集成Kruskal算法中效率极高的部分。

5.2、Kruskal 算法正确性

Kruskal 的正确性基于回路性质 和 切割定理 。

由于Kruskal算法的每一步操作（接受或拒绝）都是正确的，它最终生成的必然是最小生成树。

5.3、可视化演示

https://code.juejin.cn/pen/7571028425869049897?embed=true

5.4、代码实现

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 1. 定义并查集 (Union-Find) 类
class UnionFind:
def __init__(self, nodes):
# 初始时, 每个节点的父节点是它自己
self.parent = {node: node for node in nodes}
# 按大小合并 (优化)
self.size = {node: 1 for node in nodes}

# 查找根节点 (带路径压缩)
def find(self, i):
if self.parent[i] == i:
return i
# 路径压缩
self.parent[i] = self.find(self.parent[i])
return self.parent[i]

# 合并两个集合
def union(self, i, j):
root_i = self.find(i)
root_j = self.find(j)

if root_i != root_j:
# 按大小合并：小树合并到大树上
if self.size[root_i] < self.size[root_j]:
self.parent[root_i] = root_j
self.size[root_j] += self.size[root_i]
else:
self.parent[root_j] = root_i
self.size[root_i] += self.size[root_j]
return True # 合并成功
return False # 已在同一集合, 合并失败 (形成环)

# 2. Kruskal 算法实现
def kruskal(nodes, edges):
# nodes: ['A', 'B', …]
# edges: [ (权重, 'A', 'B'), (权重, 'B', 'C'), … ]

mst = []
total_weight = 0

# 1. 将所有边按权重从小到大排序
edges.sort()

# 2. 初始化并查集
uf = UnionFind(nodes)

# 3. 遍历排序后的边
for weight, u, v in edges:
# 4. 检查是否形成环，如果不形成环 (union 成功)
if uf.union(u, v):
# 5. 将该边加入 MST
mst.append((weight, u, v))
total_weight += weight

# 6. 当 MST 中有 V-1 条边时, 算法结束
if len(mst) == len(nodes) – 1:
break

return mst, total_weight

if __name__ == "__main__":
# 示例图 (与可视化图表一致)
all_nodes = ['A', 'B', 'C', 'D', 'E', 'F']
all_edges = [
(4, 'A', 'B'), (2, 'A', 'C'),
(5, 'B', 'C'), (10, 'B', 'D'),
(3, 'C', 'D'), (8, 'C', 'E'),
(7, 'D', 'E'), (11, 'D', 'F'),
(1, 'E', 'F')
]

mst_edges, cost = kruskal(all_nodes, all_edges)
print(f"Kruskal's MST: {mst_edges}")
print(f"Total Cost: {cost}")
# Kruskal's MST: [(1, 'E', 'F'), (2, 'A', 'C'), (3, 'C', 'D'), (4, 'A', 'B'), (7, 'D', 'E')]
# Total Cost: 17

6、Prim和Kruskal对比

Prim 和 Kruskal 都能找到最小生成树，但它们的策略和适用场景不同。

7、实际应用场景

最小生成树不仅仅是一个抽象的算法问题，它在现实世界中有着极其广泛和重要的应用。核心思想是“用最小的成本连接所有节点”。

7.1 网络设计与布线

场景：电信、有线电视、电力或计算机网络公司需要在多个地点（城市、家庭、办公室）之间铺设电缆或光纤。

应用：顶点是地点，边是连接两地的潜在路线，权重是铺设电缆的成本（例如距离、地形难度）。MST 算法可以找到一个总成本最低的布线方案，确保所有地点都被连接到网络中，且没有多余的环路（这会浪费电缆）。

7.2 电路板设计 (VLSI)

场景：在设计集成电路或印刷电路板 (PCB) 时，需要将芯片上的多个引脚（终端）用导线连接起来。

应用：将所有需要电气连接的引脚视为顶点，MST 可以用来规划导线路径，以使用最少的导线总量，从而降低材料成本、减少信号延迟和串扰。

7.3 集群分析 (数据科学)

场景：在机器学习和数据挖掘中，我们有一堆数据点（例如，客户、星星、基因），并希望将它们分成“相似”的组（集群）。

应用：将数据点视为顶点，边权重为点与点之间的“不相似度”（例如欧几里得距离）。Kruskal 算法可以被修改用于一种称为“单链接聚类”的方法。当我们按顺序添加边时，不同的连通分量（即并查集中的集合）就代表了不同的集群。通过设置一个“阈值”（例如，停止添加权重超过 10 的边），我们可以得到不同粒度的聚类结果。

7.4 近似算法 (例如旅行商问题)

场景：著名的旅行商问题 (TSP) 要求找到一条访问所有顶点一次并返回起点的最短回路。这是一个NP难问题，没有已知的快速解法。

应用：MST 本身不能解决 TSP，但它是一个非常好的“近似”工具。

• 下限：任何TSP回路的总长度必定大于或等于其MST的权重。这为评估TSP解的质量提供了一个基准。
• 近似解：通过MST（例如 Christofides 算法，它基于MST）可以构造出一个TSP路径，其长度被证明不会超过最优解的 1.5 倍。

8、总结