动机
最小生成树(minimum spanning tree)用总权重最小的边把无向带权图的所有顶点连通起来。Kruskal 算法在全局范围内挑选边,逐步生长出一片森林。Prim 算法则从选定的根出发只生长一棵连通的树,每一步都添加一条从树连向未访问顶点的最便宜的边。其正确性来自一个割上的交换论证,而高效的实现则为每个树外顶点维护当前已知的最便宜连接。
边权可以为负,也可以相等。与最短路算法不同,Prim 算法的键(key)是某一条跨越边的权重,而不是从根出发的路径长度。尽管两种算法都可以使用优先队列,这一区别仍然十分重要。
定义
定义 3.7.1
(生成树与割)
设 是有限连通无向图,,边权为实数。生成树是包含每个顶点的、连通且无圈的边集。对于非空真子集 ,若一条边的一个端点在 中而另一个端点在 外,则称该边跨越(crosses)这个割。
定义 3.7.2
(Prim 算法)
Prim 算法从属于 的一个根出发,此时尚未选取任何边。当 时,选取一条跨越割 的权重最小的边,把这条边加入已选边集,并把它在 外的端点加入 。权重相等时可以任意取舍。在连通图中,只要 非空且不等于 ,这样的边就一定存在。
定理
定理 3.7.3
(Prim 算法是正确的)
对于每个连通带权无向图,Prim 算法都会终止并输出一棵最小生成树,即使边权为负或存在相等的权重也是如此。
定理 3.7.4
(带索引的二叉堆实现)
使用邻接表和支持 extract-min 与 decrease-key(二者均为 时间)的带索引二叉最小堆,当 时,Prim 算法的运行时间为 ,空间为 。
证明思路或证明
证明
(Prim 的不变量给出最小生成树)
维护如下不变量:已选取的边在 上构成一棵树,并且被包含在某棵最小生成树 中。初始时已选边集为空,不变量成立。设 是跨越当前割的一条最小边。若 ,则同一棵最小生成树说明加入 之后不变量依然成立。否则,把 加入 会产生唯一的一个圈。 中连接 两个端点的路径跨越该割,所以这个圈中还含有另一条跨越边 。已选取的边全部位于 之内,因此 不是已选边之一。由于 ,用 替换 得到一棵权重不大于 的生成树。由 的最小性,它同样是一棵最小生成树,并且包含扩大后的已选边集。
添加一条通向一个新顶点的边,会保持已选子图的连通性与无圈性。每次迭代使 增加一,所以添加 条边之后,它就是一棵生成树。由不变量,它被包含在某棵最小生成树中;二者都有 条边,故相等。这个证明只用到边权之间的比较,因此对负权与相等权重同样成立。
证明透视
安全边保持了最优性
这个交换并不宣称所选的边属于每一棵最小树,它只是构造出一棵包含此前所有选择以及新边的最小树。论证依赖三件事。 的两个端点之间的树路径必定跨越这个割,不论权重如何,都因此得到一条可替换的边 。每条已选的边的两个端点都在 内,所以 不是已选的边,删去它保留此前所有的选择。最后,,因为 是跨越该割的最轻边,所以交换不会使权重增加。只有这一次比较涉及权重,这就是为什么负权或相同的权重都不构成困难。若 不是最轻的,交换可能使权重增加,不变量就会失效。
证明
(堆中的键是最轻的跨越边)
对于堆实现,为每个在 之外的顶点维护一个键,其值等于当前已知的从 到该顶点的最轻边的权重,同时维护一个父端点来见证这个键。根的键初始为零,其余所有键均为无穷大。每当一个顶点被取出,就扫描它的邻接表,只要新的跨越边更轻,就降低相应邻居的键。对被取出的顶点个数作归纳可知,每个有限的键都等于从当前 到该树外顶点的所有边的权重的最小值。因此最小键给出一条全局最轻的跨越边。
共有 次取出操作,且每条无向边最多被邻接表检查两次。成功的键降低至多发生 次。每次堆操作耗时 ,而图与堆的存储为 。二叉堆的高度为 ;extract-min 与 decrease-key 只沿至多一条从根到叶的路径恢复堆序。由于图连通,每个被取出的非根顶点都有一个有限的、带见证的键。
例题详解
例题 3.7.5
(生长一棵树)
对于权重为 、、 的三角形,从 出发。最轻的跨越边是 ,然后从 连向 的最轻边是 。所得的树权重为 。
例题 3.7.6
(一条负权边)
对于三边权重为 的三角形,Prim 算法可以先选取负权边。其交换证明依然适用:最小生成树是使总权重最小的生成树,而证明中从未用到权重非负的假设。
例题 3.7.7
(出现相等权重并不意味着树唯一)
在三条边权重都是一的三角形中,任意两条边都构成一棵最小生成树。不同的取舍方式可能返回不同的树,它们的总权重都是二。
常见错误
反例模式
Prim 的键不是路径距离
在边权为 和 的路径 中,加入 之后, 的 Prim 键是 ,即边 的权重。而从 到 的最短路距离是 。把键当作路径距离,就混淆了两个不同的目标。
常见错误
(连通性与优先队列的更新)
按所述方式运行的单棵树算法需要图是连通的。在非连通图上,在所有顶点都被到达之前,割可能没有任何跨越边;在每个连通分量中重新开始可以得到一个生成森林,但这需要另行规定输出的要求。优先队列必须以与当前键一致的方式支持更新;若采用另一种允许过期条目存在的实现,则需要单独分析其正确性与复杂度。
割交换的详细论证
这个不变量是存在性的:每一步之后,至少存在一棵包含所有已选边的最小生成树。权重相等可能意味着存在多棵最小生成树,而新选出的边不必属于所有这些树。交换论证足以在不假设唯一性的情况下保留一棵合适的最优树。
当一条边 连接 中的一个顶点与 外的一个顶点时,把它加入生成树 会产生唯一的一个圈。这是因为树中两个端点之间本来就有唯一的路径;这条路径加上 就是那个圈。该路径从 之内出发,终止于 之外,所以它至少含有一条跨越该割的边 。去掉 就打破了这个圈,并留下一棵连通的生成树。已选取的边的两个端点都在 中,所以它们都不可能是这条跨越边。因此这次替换保留了此前所有的选择。
如果 与 权重相等,新树的权重与原树完全相同。如果 严格更轻,新树就会比假定的最小树更轻,这是不可能发生的;而这个不等式已经足以证明存在一棵包含 的最小生成树。这一推理即使某些权重为负也同样适用。生成树的边数是固定的,并且不能重复使用同一条负权边,所以最短路径(walk)中出现的负环问题与此处无关。
例题 3.7.8
(最小生成树不必保持最短路)
取三角形,、、。从 出发的 Prim 算法先选 ,再选 ,得到权重为四的最小生成树。该树中从 到 的路径权重为四,而原图中的最短路是权重为三的直接边 。树的最小总权重与从根出发的最短距离是不同的目标。
维护堆的不变量
在根被取出之前,它的键为零,其余每个顶点的键均为无穷大。根不选取任何边。取出一个顶点 之后,把它加入 ,并扫描与它关联的边。对于每个仍在 之外的邻居 ,把边权 与 的当前键作比较。若前者更小,就更新该键,并记录 为其父节点。权重相等的边不必取代原有的父节点:原有的边仍然是一个合法的跨越边见证。
假设在加入 之前,每个树外键都等于从旧的 到该顶点的边的最小权重。加入 之后,新增的跨越边候选只有与 关联的边。扫描它们并取最小值就恢复了不变量。因此,所有树外顶点中最小的键就是所有跨越边中最小的权重,其父边是 Prim 算法的一个合法选择。这既解释了堆为何能实现抽象的算法,也说明了如果没有键的不变量,仅仅取出数值标签最小者是不够的。
带索引的堆对每个树外顶点最多保留一个有效的堆条目,并记录其位置,使 decrease-key 能够找到它。执行 extract-min 时,用最后一个条目替换根条目并将其向下移动,可沿一条高度为 的路径恢复堆序。decrease-key 则沿至多一条这样的路径把被改变的条目向上移动。通过插入 个初始条目来建堆需要 时间,在所述界限之内;线性时间建堆也是可行的,但本分析并不需要。
每条无向边都出现在其两个端点的邻接表中。随着顶点进入 ,它至多被检查两次,所以共有 次检查,成功的键降低次数也至多如此。加上 次取出操作,当 时,堆操作耗时 。堆和每个顶点的数组占用 空间,邻接表占用 。当 时,算法立即返回空边集。
非连通图与约定
如果图是非连通的,把当前连通分量与其他所有分量分隔开的割可能没有任何跨越边。一个设计为返回最小生成森林的版本,可以在每完成一个连通分量时,从一个未访问的顶点重新开始 Prim 算法。对每个连通分量分别运用连通图情形的证明可知,它们的并集是一个最小生成森林,这里最小生成森林定义为在每个连通分量中都是最小生成树。这与单棵生成树是不同的输出要求。
只要每条平行边都被检查并计入 ,平行边就是无害的;最便宜的一条可以成为键的见证。自环永远不跨越任何割,也不可能属于生成树,所以可以忽略。如果输入的表示中含有自环,邻接表扫描必须避免把它当作通向树外顶点的边。这些约定不影响交换证明。
对于只有一个顶点的连通图,空边集是它唯一的生成树,总权重为零。对于含有若干孤立顶点的非连通图,生成森林对每个顶点各有一个单点分量,且没有边。明确说明这些边界情形,可以避免堆实现试图为根添加一条父边。
比较算法的保证
Prim 与 Kruskal 都使用安全边论证,但它们当前维护的结构不同。Prim 维护一个连通集 ,并在它的割上做选择;Kruskal 维护一片森林,按全局的权重顺序考虑各条边,并拒绝会产生圈的边。两种算法都不要求所有权重互不相同。不同的取舍方式可能产生不同的最小生成树,所以在存在相等权重时,比较边的列表不是可靠的正确性检验;应当比较总权重,并验证树的性质,或使用合适的证书。
最小生成树优化的是所选边之和。如三角形的例子所示,它不一定使从根到各顶点的路线最短。Dijkstra 算法维护的是临时路径长度,其假设与不变量都不同。共用最小堆并不意味着这两种键的含义可以互换。
常见错误
(有效的生成树不一定是最小的)
对一次有限的运行,可以通过确认它选取了 条边、没有圈且连通所有顶点来检查其基本有效性。这些条件证明的是它是一棵生成树,而不是最小的。最优性由 Prim 各步选择的交换证明提供。对于另行给出的一棵树,则需要额外的最小树证书或比较算法才能确立其最优性。
验证给定生成树及其唯一性
假设有人给出一棵生成树 ,但没有说明它如何得到。对每条端点不同的非树边 ,记 为 中连接两端点的唯一路径。加入 后,这条路径和 一起形成一个圈。可以检验以下条件:
这个条件是 为最小生成树的充要条件,权重相等或为负数也适用;自环不属于任何生成树,可忽略。若不存在非树、非自环边,条件自动成立,而且 是唯一的生成树。
定理 3.7.9
(最小生成树的圈证书)
生成树 是最小生成树,当且仅当对每条非树、非自环边 ,都有 。当且仅当每个这样的不等式都严格成立时, 才是唯一的最小生成树。
证明
(证书刻画最小树与唯一性)
必要性:若某条 比路径上的某条边 更轻,加入 、删除 就得到更轻的生成树。充分性:任取生成树 。若 ,取 ,从 删除 得到一个割。 中连接 两端的路径必定跨越此割,取其中一条跨割边 。 是 唯一的跨割边,所以 ,而 中连接 两端的路径必含 。由上述条件,。在 中用 替换 ,得到一棵权重不增加、且与 多一条共同边的生成树。重复这个过程直到得到 ,便知对任意 都有 。
同一论证还给出唯一性: 是唯一最小生成树,当且仅当上述比较全部严格。若某条非树边 与路径上的最大权边 等重,交换它们便得到另一棵同权生成树。反过来,若比较全部严格,对任意 ,上述第一次替换就严格减轻权重。因此边权互异足以保证唯一,但并非必要条件。
例题 3.7.10
(权重相等时的最优性检验)
在三角形中令 、,并取 。唯一的非树边是 ;它的树路径上最大边权为 ,严格小于 。所以 是唯一的最小生成树,尽管两条边权相等。若改为 ,就可用 替换任一条路径边,得到另一棵最小生成树。若改为 ,条件不成立,用 替换 会使总权重从 降至 。
使用此检验前,必须先确认 是生成树;单靠路径比较不能证明连通和无圈。每次重新遍历树来求路径最大值,是直接的多项式时间方法;更快的数据结构需要另行分析。
总结
Prim 算法利用当前割上的一条最轻边来生长一棵连通的树。交换论证维持了它与某棵最小生成树的相容性。带索引的堆为每个树外顶点维护最便宜的跨越边,并给出所述的邻接表复杂度。
练习
快速检查
(在含有 个顶点的连通图上,Prim 算法添加多少条边?)
每添加一条边就带进一个新顶点。
解答 · 答案
它添加 条边,即根之外的每个顶点各对应一条。
快速检查
(负权边会使割交换证明失效吗?)
证明对权重作了哪一个比较?
解答 · 答案
不会。证明只用到所选的跨越边不比被交换掉的跨越边更重。
快速检查
(一个顶点的 Prim 键代表什么?)
它是路径长度,还是单条边的权重?
解答 · 答案
它是从当前的树到该树外顶点的单条边的已知最小权重。
快速检查
(为什么在连通图上,终止之前必然存在一条跨越边?)
缺少跨越边对路径意味着什么?
解答 · 答案
如果某个非空真子集没有任何边跨越,那么从该子集到其补集就没有路径,这与图的连通性矛盾。
练习 3.7.11
(一个图有树边 ,权重依次为 ;非树边 的权重依次为 。 是否最小?是否唯一?若有另一棵最小树,请写出。)
核心
对每条非树边使用圈证书。
解答(3)
- 1
比较 与它的树路径
关键一步
从 到 的树路径是 ,最大权重为 ,而 。这个比较以等号成立。
依据: 非树边的权重必须不小于其树路径上最重的边。
- 2
比较 与它的树路径
从 到 的树路径是 ,最大权重为 ,而 。
- 3
得出最小性与唯一性
两个不等式都成立,所以 是最小的。 处的等号允许用 取代 ,得到 ,这是另一棵总权重同为 的生成树。因此 是最小的,但不唯一。