会改变的划分
向无向图逐条加入边时,分量测试会问两个端点是否已经连通。前面的 Kruskal 单元使用简单标签扫描;不相交集合森林则用父指针表示相同划分,合并时无需重新标记每个顶点。
定义 4.4.1
(不相交集合、find 与 union)
固定 个元素,起初每个元素各自成集合。操作 返回 所在集合的代表; 合并二者所在集合。代表不必是最小元素,合并后也可能改变。两元素在同一集合,当且仅当它们当前的代表相同。
父指针森林与规则
定义 4.4.2
(带大小标记的父指针森林)
每个元素存储一个父指针。根指向自身;沿父指针最终到达根。每个根另存其树的元素数目。起初每个元素都是大小为一的根。查找代表时沿父指针到根;合并时先找两个根,若相同则不作改变。否则把较小树的根接到较大树的根之下,并把两个大小相加存到保留的根;相等时任意决定。非根所存的大小无需查用。
命题 4.4.3
(森林表示划分)
经过任意一串合并之后,森林中的树恰好是当前的各个集合,而每个根所存的数目就是它的树的元素个数。
证明
(对操作作归纳的不变量)
起初每棵树是一个集合,每个根的大小为一。把一个根接到另一个根之下,恰好合并含有这两个根的两棵树;由于两个根不同,不会形成环。其他树都不变。这与两个集合的合并相符。若两次查找的结果相同,合并不作任何改变,而这两个元素本来就在同一集合。因此对操作的次数作归纳,可知森林中的树恰好是当前集合。保留根的大小用加法更新,等于合并后树的元素个数,所以大小不变量也得以保持。
定理 4.4.4
(不压缩路径时的对数深度)
若按大小合并且不使用路径压缩,每条父指针路径最多有 条边。因此在数组访问为常数时间的模型下,每次查找以及包含两次查找的合并均需 时间。
证明
(元素的深度每增加一次,其所在的树至少翻倍)
固定元素 。只有当其当前树的根接到另一个不同的根之下时, 的深度才增加,而且恰好增加一。接上之前,其树不大于另一棵树;接上之后,合并树至少有先前两倍元素。在两次深度增加之间,树只会变大。从大小一开始且永不超过 ,深度最多增加 次。相同大小时无论选哪个根,证明都成立。一次查找沿一条父指针路径走,其长度至多是这个深度界,加上读取根的常数工作;一次合并则作两次查找和常数量的其他工作。
证明透视
倍增论证用到什么
真正起作用的量,是含 的那棵树的大小。它从一开始,从不超过 ,并在每次使 下降一层的连接时翻倍;具备这三个性质的量,只能翻倍 次。翻倍完全来自连接时的大小规则:由于被移到下面的是较小的树,含 的树至多是合并后树的一半。允许相等,所以平局时怎么选都无所谓。
若把规则反过来,让较大的树接到较小的树之下, 所在的树可以很大,而合并后的树却只多了一个元素,翻倍便失效。这里的查找从不改变指针,所以除了连接之外,没有任何步骤会改变深度。一次连接把整棵树恰好下移一层,因此 的深度就是把它所在的树下移的连接次数,而从 出发的查找,路径长度等于这个深度。
操作例子
例题 4.4.5
(追踪非根父结点)
从单元素集合 开始;相同大小时把第二个所列根接到第一个之下。执行 和 后,根 的大小均为二。执行 后,根 大小为四,而 沿 到根。再合并 ,接着将其大小为二的树与 的大小四之树合并:无论参数次序,根 都接到 之下。最后大小为六; 的深度均为二。
例题 4.4.6
(倍增界可以达到)
取八个元素 ,相同大小时把第二个所列根接到第一个之下。依次执行 、、、,得到四个大小为二的根 。再执行 与 ,得到两个大小为四的根 ,最后 得到大小为八的唯一根 。从 出发的路径是 ,共三条边,等于 。这里每次合并的两棵树大小相同,所以每次都把最深的元素再推下一层。
例题 4.4.7
(形成环的边不改变任何东西)
在六元素的例子中依次插入无向边 –、–、–,然后是 –。前三次 建成以 为根、大小为四的树。对 –, 沿 , 沿 ,两者都返回 ,所以该次调用不作任何事,大小也不变。这条边在图中形成一个环,而分量结构与之前相同:集合 加上 与 。
界的适用范围
命题 4.4.8
(一串操作的成本)
初始化数组需 。之后 次操作的总最坏成本为 ,数组使用 空间。
证明
(只初始化一次,再逐个操作估算)
把每个元素的父指针设为自身、大小设为一,需要 时间,并使用两个长度为 的数组。 次操作中每一次都是一次查找,或是带两次查找的一次合并,而按深度定理,每次成本为 。把成本相加即得上界。
对数界来自明确的按大小规则。路径压缩会在查找时改变指针,需要另行分析,因此这里不声称反 Ackermann 界。
反例模式
不用大小规则的连接可以造成长链
假设每次 都不看大小,直接把 的根接到 的根之下。取 ,依次调用 、,直至 。第一次令 的父结点为 ,第二次令 的父结点为 ,依此类推,所以从 出发的路径是 ,共七条边,大于 。在大小规则下,同一串操作仍然很浅:每次调用都把大小为一的树接到大的根之下,没有任何路径多于一条边。深度定理依赖这条规则;任意接根可产生长链,对元素 作一次查找便需七步指针。
常见错误
(比较直接父结点而不是根)
在第一个例子中, 的直接父结点是 ,代表却是 。即使两个元素的父路径到达同一个根,只比较直接父结点也可能误判为不同集合。分量测试必须使用根,而不是只走一步指针。
常见错误
(读取非根的大小)
只有根所存的大小才有意义。在第一个例子中,执行 之后, 仍存着数字二,但它的树已经属于一个大小为四、根为 的集合。若之后的合并拿 所存的数字与另一个根的大小比较,可能接错方向,并破坏倍增论证。必须比较两个根所存的大小。
若要在插入边的过程中维护无向连通性,对每条新边的端点执行合并,查询时比较两次查找。
命题 4.4.9
(插入边时的连通性)
若逐条插入无向图的边,且每次插入 时都调用 ,则每次插入之后,所维护的划分都等于图的连通分量划分。
证明
(一次插入要么合并两个分量,要么不改变任何东西)
起初没有边,每个顶点各自是一个分量,与单元素集合相符。插入边 不会在 、 所在分量以外的顶点之间添加任何连通关系。若 与 本来就在同一分量,各分量不变,合并也不作改变。否则两个分量变成一个,而合并恰好合并对应的两个集合。对插入次数归纳即得结论。
此结构本身不支持删边:删去桥边可能把一个已维护集合分成两个;它也不回答有向可达性,因为后者一般不是等价关系。
练习
快速检查
(大小三的树与大小七的树合并,哪个根成为父结点?新大小是多少?)
较小的根接到较大的根之下。
解答 · 答案
把大小三的根接到大小七的根之下;保留根的大小为十。
快速检查
(当 ,倍增界给出什么最大深度?)
套用 。
解答 · 答案
最多 条父边。
快速检查
(在例子中,为什么 返回 ,尽管 的直接父结点是 ?)
沿着指针一直往上走。
解答 · 答案
查找沿 到达根 ;中间父指针本身不是代表。
快速检查
(加入唯一的无向边 – 后,为什么删除它不能只保持不相交集合结构不变?)
比较删除前后的连通情况。
解答 · 答案
有该边时 连通,删除后不连通;不变的结构仍把它们放在同一集合,因此需要其他方法或重建。