动机
许多图算法需要反复询问:两个顶点是否已经被目前选出的边连通。每加入一条边就重新计算连通分量,会浪费已有的信息。不相交集合结构维护顶点集合的一个划分,并支持两种操作:查找某个集合的代表元,以及合并两个集合。
其实现是一片由父指针构成的森林。效率取决于如何链接各棵树:若总是把一个根接到另一个根之下,可能形成一条很长的链;而若把较小的树接到较大的树之下,则任何顶点的深度能够增加的次数都受到限制。倍增论证给出一个具体的对数界,而无需假定更强的反阿克曼函数(inverse-Ackermann)定理。
定义
定义 3.8.1
(不相交集合森林、查找与合并)
开始时有 个单元素集合,每个元素一个。每棵树的根以自身为父节点;其余每个节点指向它的父节点。同一棵树中的元素构成一个集合,根是该集合的代表元。操作 find(x) 从 出发沿父指针走到其根。操作 union(x,y) 先找出两个根。若两根不同,则把较小的树的根链接到较大的树的根之下,并更新较大根所存储的大小。大小相等时可任意决定。对已在同一棵树中的元素做合并,不产生任何改变。
定义 3.8.2
(深度与所存储的大小)
节点的深度是它到根的路径上的父边数目。根所存储的大小是其所在树中的元素个数。我们先分析不带路径压缩的按大小合并;之后再把压缩作为可选的修改来讨论。
定理
定理 3.8.3
(按大小合并的高度界)
从 棵单元素树出发并使用按大小合并,则每个节点的深度至多为 。在父指针模型中,每次查找耗时 ,每次合并(包括其中的两次查找)耗时 。
定理 3.8.4
(Kruskal 算法的分量测试)
在无向图中,按边权非递减的顺序处理各边,并且当且仅当某条边的两个端点具有不同的不相交集合代表元时才接受该边,则所得结果是一个最小生成森林。对于连通图,所得结果是一棵最小生成树。
证明:深度增加迫使集合倍增
证明
(按大小合并使集合在每次深度增加时倍增)
固定一个元素 。只有当 当前所在树的根被接到另一个根之下时,它的深度才会增加。在这样的合并中,另一棵树的节点数至少与 所在的树一样多。因此,包含 的新树的节点数至少是原来的两倍。此后的合并永远不会使集合变小。
起初 位于大小为一的树中,深度为零。经过 次深度增加之后,它所在的树的大小至少为 。任何树所含元素都不超过 个,故 ,从而 。这一推理适用于每个元素,尽管不同元素可能在不同的合并中经历深度增加。
一次查找至多沿着上述数目的父边前进,再加上最后对根的检查。一次合并执行两次查找,以及常数量的大小比较、指针更改和大小更新。由此得到所述的时间界。当 时,没有可供查找或合并的有效元素;深度的结论针对非空结构。
证明透视
为什么较小的树很重要
这个证明跟踪单个节点,计算它的深度最多能增长多少次。关键一步是把每一次增加都归因于该节点所在集合的一次倍增。只有当节点所在树的根被连到另一个根之下时,深度才加一;大小规则使接收的树至少一样大,所以合并后的集合至少是原来的两倍。证明用到三件事:大小规则、集合只会合并而不会缩小,以及从单元素开始(大小为一、深度为零)。界 使论证收尾,因为没有集合可以超过 个元素。若去掉大小规则,大树就可能被连到单元素之下,使大树中每个节点的深度加一,而集合只多了一个元素。下面反例中的链就是这样产生的。
证明:不相交集合的不变量
证明
(森林跟踪被接受的边的连通分量)
在处理任何边之前,已选边构成的图没有边,其连通分量就是单个顶点。不相交集合森林恰好表示这些分量。假设在处理边 之前这一点成立。
若 与 具有相同的代表元,则已选的边之中已含有连接它们的一条路径。加入 会产生圈,所以算法拒绝该边,分量划分保持不变。若代表元不同,则加入 会连接两个分量,且不会形成圈。合并操作恰好合并这两个被表示的集合,因此不变量依然成立。
证明
(割交换给出最小生成森林)
于是,被接受的边恰好是 Kruskal 算法所作的无圈选择。其最优性由标准的割交换论证证明:被接受的边是穿过当前某个分量所对应的割的最小权边。任何先前扫描且跨越当前分量的边,在扫描时两端也处于不同分量,因为分量只会合并;它因而会被接受。由排序顺序,其余跨割边的权都不小于当前边。若包含先前已接受各边的某个最优生成森林不含该边,则把它加入后会与另一条权不更小的穿过割的边形成圈;交换这两条边后仍得到生成森林,且其权不增加。通过归纳,可始终保留一个包含所有已接受边的最优森林。
所有边都考察完毕后,原图的每个连通分量都由被接受的边连通:否则,位于剩余两个分量之间某条路径上的某条原图的边,在被扫描时就应当已被接受。因此,被接受的森林在原图的每个分量中都是生成的,而交换不变量保证其权最小。权相等以及负权都不会使割论证失效。
例题详解
例题 3.8.5
(一次大小倍增的追踪)
从单元素集合 开始。合并 ,并另外合并 ;所得的两棵树大小均为二。再合并它们的根,平局时把第二个根放在第一个根之下。第二棵树中的叶子现在深度为二,其所在集合的大小为四。深度界为 。
例题 3.8.6
(一次多余的合并)
当 和 已在同一棵树中后,union(a,b) 两次找到同一个根,不做任何链接。若再次更新大小就是错误的:所表示的集合并没有增加任何元素。所存储的大小必须始终等于该树中不同节点的个数。
例题 3.8.7
(Kruskal 算法中的三角形)
对于三角形的边 ,权分别为 ,接受 并合并 ,然后接受 并合并其所在分量。扫描到 时,其端点具有相同的代表元,因此拒绝该边。所得生成树的总权为三。
例题 3.8.8
(一个不连通的图)
设图中有一条连接 的权为 的边,以及一个孤立顶点 。Kruskal 算法接受该边,并让 保持为单点树。答案是一个有两个分量的最小生成森林,而不是整个图的生成树。
路径压缩
路径压缩修改 find(x):在找到根之后,把途经的节点都重新指向根。它保持所表示的划分不变:每个被重定向的指针仍在同一棵树之内,并且通向同一个根。所存储的根的大小仍然有效,因为没有元素改变所属集合。压缩在施行的那一刻只会缩短节点的路径。
按大小合并再加上路径压缩可以得到更强的摊还界,但该定理需要另行分析,并需要精确的操作序列模型。上述初等的倍增论证已经给出对数界:在按大小合并引起深度增加之后,包含该节点的集合已经翻倍;压缩可以去掉一些父边,但不会产生使深度增加的新父边。我们在此不推导也不声称更强的界。
代表元是实现上的选择。两次都正确的运行如果平局处理方式不同,可能为同一个集合给出不同的根。程序应当比较同一结构内返回的代表元,而不应依赖某个特定顶点永远是某个连通分量的名称。
常见错误
反例模式
任意链接可能产生一条链
从单元素的根 出发,反复把当前的根接到下一个单元素根之下。结果是一条链,其中 的深度为 。对数界的证明在此失效,因为包含 的树每次都被接到更小的树之下,所以每次深度增加时其大小并不翻倍。
常见错误
(支持合并,不支持删除)
不相交集合结构支持合并,但不支持一般的删边。删除一条已接受的图的边可能使一个连通分量分裂,仅凭这些父指针无法支持这种操作。Kruskal 算法中的用法是有效的,因为它只加入被接受的边。
常见错误
(大小与秩是不同的量)
按大小合并与按秩合并是相关的策略,但它们所存储的量含义不同。根的大小是当前集合的基数。在另一种实现中使用的秩,除非确实被维护为大小,否则不应称为大小。
图算法的代价
设图有 个顶点和 条边。对边排序需要 次比较。初始化单元素集合需要 时间。 条边中每条引起两次查找和至多一次根链接,因此当 时,初等界给出额外的 时间。总时间为 ; 时的常数已被 的形式涵盖。
对边排序与不相交集合操作所做的是不同的工作。更快的合并并不能免去在此实现中对任意权排序的需要。反过来,如果边已经排好序,这一输入条件可以省去排序,但连通性操作及其正确性不变量仍然必不可少。
所存储的信息保证了什么
只有根的大小需要是最新的。当两个根被链接时,子根处的旧大小可以留在内存中,但之后不得再把它当作某个独立集合的大小。在合并比较大小之前,查找会沿父链走到当前的根。实现中可以为清晰起见清除旧值,但正确性取决于只在当前的根处查询大小。
常见错误
(父指针并不是输入的边)
这片森林是对划分的辅助表示,并不一定是输入图的子图。父指针记录的是哪个代表元被链接到另一个之下;它不必是引起该合并的图的边之一。因此父链不一定是原图中的路径。若要输出最小生成森林,应单独保存被接受的图的边。
例如,若一条被接受的边连接顶点 和 ,实现链接的是它们所在两个集合的根。这些根可能既不是 也不是 。合并仍然是正确的,因为这条图的边连接了两个被表示的分量,而父指针只是记录它们的合并。最小总权的证明涉及的是被接受的图的边,而不是父指针的任意方向。
总结
按大小合并迫使一个集合在其某个节点下降一层时至少翻倍,从而得到对数级的高度。不相交集合划分追踪被接受森林的分量,而割交换论证证明了 Kruskal 算法的最优性。路径压缩保持连通性,但其更强的摊还分析是另一个独立的结果。
练习
快速检查
(有八个单元素时,按大小合并定理所允许的最大深度是多少?)
对 计算 。
解答 · 答案
界为 。反复合并大小相同的树,并沿着被连到另一个根之下的那棵树中的一片叶走,就可以达到这个界。
快速检查
(为什么成功的合并会把新根处的大小更新为两个旧大小之和?)
两个根分别表示哪些集合?
解答 · 答案
两个根所表示的集合互不相交。链接它们把这两个集合合并,既不重复也不删除元素,所以基数相加。若两个元素的根相同,则没有合并不同的集合,不可以把大小相加。
快速检查
(在三角形的例子中,即使第三条边的权重与第二条边相同,为什么它仍被拒绝?)
比较它两个端点的代表元。
解答 · 答案
接受前两条边之后,第三条边的端点已经由被选中的路径连通。加入第三条边会产生圈。代表元相等就能检测出这一点,与权重是否相同无关。
快速检查
(经过一次带路径压缩的查找之后,根所存储的大小会怎样?)
压缩会增加或移除元素吗?
解答 · 答案
保持不变。压缩改变的是同一集合内的父指针,并没有增加或移除元素。只有对不同集合的成功合并才会改变根所存储的基数。
练习 3.8.9
(对合并次数作归纳,证明:在按大小合并且不作压缩时,每棵高度为 的树至少有 个节点。)
核心证明
树的高度是其节点的最大深度。大小相同时,可以任意决定链接的方向。
提示(1)
链接两棵树时,新的高度是接收树的高度与被链接树的高度加一之中较大的一个。
解答(3)
- 1
检查起始的树
单元素树的高度为 ,节点数为 。
依据: 每棵树都从单元素开始。
- 2
把较小的树 连到 的根之下
关键一步
设 的高度为 ,并且都满足结论。链接后的树 的高度为 ,且 。
依据: 按大小合并保证 。
- 3
分两种情形讨论高度
∎若 ,则 。若 ,则 。两种情形都有 ,所以每次合并之后结论依然成立。