网络设计者要用成本最低的一组连接把 个站点连起来,每条可能的连接都有成本。答案就是最小生成树。两个经典算法都能构造最小生成树,两者的正确性都建基于同一个结构性事实,即割性质。Kruskal 算法还需要一个记录“哪些顶点已经连通”的数据结构,即不相交集合并查集(union–find)。本节只在比较时提及 Dijkstra 算法的最短路径想法;主要的先备知识是连通性与遍历各节的图论词汇:连通、圈、树与连通分量。
1. 生成树与问题
定义 18.1.1
(生成树与最小生成树)
设 为有限、连通的无向图,有 个顶点,每条边有实数权重 。允许平行边;自环永远无用,予以忽略。生成树是边集 ,使 连通且无圈。每棵生成树恰有 条边,并且向生成树加入任何一条非树边,恰好产生一个圈。最小生成树(MST)是总权重 最小的生成树。权重相同时可能有多棵最小生成树,但它们的总权重一样。权重可以为负;只有大小次序重要。
定义 18.1.2
(割、横跨边与尊重割的边集)
割是把顶点分成两个非空部分 。若一条边的两个端点分属两部分,就说它横跨该割。若边集 中没有边横跨某个割,就说 尊重该割。
2. 割性质
定理 18.1.3
(割性质)
设 ,其中 为某棵最小生成树。设 是 所尊重的割, 是所有横跨该割的边中权重最小的一条。则存在最小生成树 使 。
证明
(以最轻横跨边换走圈上的一条边)
若 ,取 。否则 恰含一个圈,且它经过 。这个圈从割的一侧出发又回到同一侧,所以横跨该割的次数为偶数; 是其中一次,因此圈上还有另一条横跨的边 ,且 (圈上除 外的边都在 中)。因 尊重该割,。由 的选取,。令 。从 中去掉 得到两个连通分量,而 在 的唯一圈上,所以 的两个端点属于不同分量;故 连通且有 条边,是生成树。其权重为 ,所以 是最小生成树,并包含 。
证明透视
割性质各项假设的用处
中有圈,是因为 而 是生成树。 横跨该割,加上圈横跨割的次数是偶数,就得出圈上另一条横跨边 。“ 尊重该割”只用了一次:它说明 ,所以删去 不会删走 的任何边。 在横跨边中最轻这一点也只用了一次:它给出 ,所以交换不会增加权重。最后, 在圈上,所以 把 的两个连通分量重新接上,结果仍是生成树。
这是一个交换论证:从任意一个最优解出发,把其中一个元素换成贪心的选择,而不损失最优性。因此,若贪心算法每一步都加入割性质所认可的边,就能维持不变量“已选的边包含于某棵最小生成树”。
反例模式
“尊重割”的假设不能去掉
声称:若 含于某棵最小生成树,而 是横跨某个割的最轻边,则不论 是否尊重该割, 都含于某棵最小生成树。取顶点 上的三角形,三条边的权重都是 。那么 是权重为 的最小生成树。对割 ,横跨边为 与 ,权重都是 ,所以 是横跨该割的最轻边。但 含有横跨边 ,而 是整个三角形,含有圈,不含于任何生成树。修正方法是加上“ 尊重该割”的假设:此时证明中被删去的边 绝不在 内。
3. 不相交集合并查集
定义 18.1.4
(不相交集合并查集)
不相交集合结构维护 的一个划分,支持 find(x)(返回包含 的集合的代表元;在该集合改变之前,同一集合的所有元素返回相同的代表元)与 union(x,y)(合并两个集合)。
把每个集合表示为存于数组 parent 中的有根树:根 满足 parent[r]=r 并作为代表元,另为根记录 size[r]。
make: parent[i] = i; size[i] = 1 for each i
find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
union(x, y):
a = find(x); b = find(y)
if a == b: return false
if size[a] < size[b]: swap a, b
parent[b] = a; size[a] = size[a] + size[b]
return true
引理 18.1.5
(按大小合并限制深度)
若只使用按大小合并,每棵树的深度至多为 ,所以 find 耗时 。
证明
(深度只在树大小加倍时增加)
顶点 的深度只会在它所在树的根被挂到另一个根之下时加一,而这只在 所在树的大小不超过另一棵树时发生;合并后的树大小至少是原先 所在树的两倍。一棵树至多有 个顶点,所以 所在树的大小至多翻倍 次。故深度至多为 。
路径减半只会缩短路径,所以引理的深度上界依然成立。另有一个标准结果(此处引用而不证明):按大小合并加上路径压缩或路径减半,对 个元素执行 次操作的总时间为 ,其中 为反 Ackermann 函数,对内存容得下的任何输入都小于 5。本节把每次操作视为 已足以得出下面的界。
4. Kruskal 算法
sort edges so that w(e_1) <= w(e_2) <= ... <= w(e_m)
T = empty; make the disjoint sets
for i = 1..m:
(u, v) = e_i
if union(u, v): add e_i to T
return T
一条边被接受,当且仅当它的两个端点位于当前森林 的不同连通分量。
定理 18.1.6
(Kruskal 算法的正确性)
对连通图,Kruskal 算法返回一棵最小生成树。
证明
(每条被接受的边都是最轻的横跨边)
以归纳法证明每一步之后边集 都包含于某棵最小生成树。起初 。设边 被接受,且 ( 为某棵最小生成树)。令 为 中包含 的连通分量的顶点集,则 。 中没有边横跨 ,所以 尊重此割,而 横跨它。设 是另一条横跨此割的边。若 在排序中较早,它不在 中( 没有边横跨此割),所以它当时已被检查而被拒绝,表示当时森林已把它的两个端点连通;森林只会增大,所以它的端点现在仍在同一分量内,但 横跨该割,矛盾。因此除 外,所有横跨的边在次序中都较后,。故 是横跨该割的最小权重边,由割性质, 包含于某棵最小生成树。被拒绝的边不加入,不变量保持。
结束时 是森林。假设它有至少两个分量。因 连通, 中有一条边 连接两个不同的最终分量。检查 时,它的端点已在不同分量(分量只会合并),所以 会被接受,矛盾。因此 是包含于某棵最小生成树的生成树,即它本身就是最小生成树。
证明透视
为什么被接受的边是最轻的横跨边
不寻常的一步,是从算法的状态取出一个割:取 为当前森林中 所在的连通分量,于是森林按构造尊重这个割。然后有两个事实使 成为最轻的横跨边。次序已排好,所以较后检查的横跨边至少一样重。而连通分量只会合并,所以较早检查的横跨边只会在端点已连通时才被拒绝,但横跨边的端点从不连通;因此没有横跨边在 之前。最后的论证是独立的,用到 连通:连接两个最终分量的边必会被接受。没有排好的次序,割论证就什么也得不到。
若 不连通,同一算法返回最小生成森林。
复杂度。 排序耗时 ;在没有平行边时 ,故为 。 次并查集操作按引理耗时 ,用所引用的结果则为 。总计 ,即没有平行边时为 。
概念视角结构
生成树记录了每一个阈值
对每个实数 ,令 为顶点集 上只含权重不超过 的边的图。Kruskal 检查完所有这些边之后,每条被拒绝的边的端点早已连通,每条被接受的边都连接了两个连通分量,所以森林与 有相同的连通分量。因此两个顶点在 中连通,当且仅当它们之间的树上路径的权重全都不超过 :该路径上最重的边,就是两顶点开始连通的最小阈值。在下面的例题中,顶点 与 在 中不连通,在 中连通,而它们的树上路径最重的边正是 。
5. Prim 算法
Prim 算法从根 起生长单一棵树。维护顶点集 (起初为 )与树 。反复选取恰有一个端点在 内的最小权重边,把它与其新端点加入。
用二叉堆存放候选边 ,按权重排序:先把 的所有出边推入;反复弹出最小者,若 就丢弃,否则把 加入 ,把该边加入 ,并把 到 之外顶点的所有边推入。
正确性。 每一步树边都在 之内,所以它们尊重割 ;所选的边是横跨该割的最小权重边,割性质维持不变量“ 包含于某棵最小生成树”。加入 条边后, 是包含于某棵最小生成树的生成树。堆中至多有 个条目,所以时间为 ,没有平行边时即 。其结构与 Dijkstra 算法相似,但顶点的键是单一条连接边的权重,而不是路径长度。
6. 例题:Kruskal 与并查集的追踪
例题 18.1.7
(Kruskal 与并查集追踪)
顶点 ,边为 (4)、(1)、(2)、(5)、(8)、(10)、(3)。按权重排序:(1)、(2)、(3)、(4)、(5)、(8)、(10)。大小相同时,union(x,y) 把 的根挂到 的根之下。
- :根为 1 与 3,大小同为 1,打成平手;
parent[3]=1,size[1]=2。接受。 - :
find(2)=2,find(3)=1;2 所在树大小为 1,小于 2,故parent[2]=1,size[1]=3。接受。 - :平手;
parent[5]=4,size[4]=2。接受。 - :两个根都是 1。拒绝(它会闭合圈 )。
- :
find(2)=1(大小 3),find(4)=4(大小 2);parent[4]=1,size[1]=5。接受。 - :根相同。拒绝。7. :根相同。拒绝。
最小生成树为 ,权重 ,共 条边。
例题 18.1.8
(不连通的图得出森林)
取顶点 与边 (1)、(2)。Kruskal 接受 ,因为 find(1) 与 find(2) 不同;同样地接受 。输出有 条边,但 个顶点上的生成树需要 条。由于没有边连接 与 ,这两个分量永不合并,所以输出是权重为 的最小生成森林。一般而言, 个顶点、 个连通分量的森林有 条边,所以接受的边少于 条,就表示图不连通。
7. 例题:同一个图上的 Prim
例题 18.1.9
(同一个图上的 Prim)
从 开始。
- :横跨边 (4)、(1)。选 。
- :横跨边 (4)、(2)、(8)、(10)。选 。
- :横跨边 (5)、(8)、(10)。选 。
- :横跨边 (10)、(3)。选 。
总权重 ,与 Kruskal 得到的是同一棵树。
8. 常见错误
- 把 Kruskal 被拒绝的边视为错误:它们正是端点已经连通的边。
- 把两个算法用于有向图。最小生成树形图需要另一种算法。
- 在不连通的图上运行 Prim 或 Kruskal 并期望得到一棵树:结果是每个连通分量一棵树的森林。
常见错误
(重用过时的 find 结果)
根会随着合并而改变,所以为前一条边算出的 find 结果可能已过时。每条边在被检查的当刻都要重新调用 find。
常见错误
(以为最小生成树必定唯一)
当所有权重互不相同时,最小生成树是唯一的,最后一道练习会证明这一点。有并列权重时未必唯一:三条边权重都是 的三角形有三棵最小生成树,每两条边一棵,权重都是 。
常见错误
(从最小生成树读出最短路径)
最小生成树使总权重最小,并不使距离最小。对 、、 的三角形,唯一的最小生成树是 ,其中从 到 的路径长度为 ,而边 的长度为 。
练习
练习 18.1.10
(顶点 ,边 (3)、(1)、(3)、(2)、(4)。求最小生成树的权重,并列出所有最小生成树。)
核心
解答(3)
- 1
对排序后的边运行 Kruskal
排序:(1)、(2),然后是 与 (3),最后是 (4)。Kruskal 接受 与 ,得到分量 与 。下一条边 或 把它们连起来,所以共接受三条边,权重为 。
- 2
说明不存在更轻的生成树
关键一步
边的权重由小到大为 ,所以任何三条不同的边,权重至少是 。
依据: 每棵生成树恰有 条边。
- 3
列出所有最小生成树
权重 要求边的权重为 、,再加上两条权重为 的边之一。 与 都是树。所以最小生成树的权重为 ,最小生成树恰好是这两棵。
快速检查
(从单元素集合 出发,使用按大小合并,平手时把 的根挂到 的根之下,依次执行 union(1,2)、union(3,4)、union(1,3)。给出 parent 数组与顶点 4 的深度。)
记录各个根的大小。
解答 · 答案
union(1,2):平手,parent[2]=1,size[1]=2。union(3,4):平手,parent[4]=3,size[3]=2。union(1,3):根为 1 与 3,大小都是 2,平手,parent[3]=1,size[1]=4。顶点 的 parent 数组为 。顶点 4 经 ,深度为 2,等于 ,即引理的上界。
快速检查
(在第一道练习的图(边 (3)、(1)、(3)、(2)、(4))上从顶点 运行 Prim,并给出总权重。)
列出每一步的横跨边。
解答 · 答案
:横跨 (3)、(1);取 。:横跨 (3)、(3)、(4);取 或 (平手,取 )。:横跨 (2)、(4);取 。总权重 ,与 Kruskal 的结果一致。
练习 18.1.11
(证明:若连通图的所有边权重互不相同,则其最小生成树唯一。)
综合证明
解答(4)
- 1
假设有两棵不同的最小生成树,取只属于其中一棵的最轻边
设 都是最小生成树,令 为恰好属于其中一棵的最轻边。由于两者地位对称,不妨设 。
依据: 权重互不相同,所以这条边是唯一的。
- 2
找出圈与一条不在 内的边
集合 含有经过 的圈。这个圈上有一条边 ,否则圈整个在 内,而 无圈。于是 且 ,所以 恰好属于其中一棵树。
- 3
比较权重
关键一步
因此 。
依据: 是恰好属于一棵树的边中最轻的,而且权重互不相同。
- 4
交换得出更轻的树
∎由于 在 的唯一圈上, 是生成树,其权重为 。这与 是最小生成树矛盾。