COMP3121 Week03 学习笔记

01 · 本周地图：从局部选择到图上的全局结构

这个部分回答什么问题：这份 PDF 的剩余内容怎样连成一条学习线？第二周笔记已用录音核对到基站覆盖的证明思路，并把 p37–38 作为自学补全。本页简短回顾这两页，重点新增 p41–153。文件存放在 week2 文件夹不代表全部属于第二周；这里的 Week03 是按你的学习编排命名，尚未核实学校正式周次。PDF 页脚编号通常比阅读器的实际页码小 1，本页的 p 均指实际页。

02 · 基站证明的收尾：比较第 k 座的位置

这个部分回答什么问题：从第二周的最左未覆盖房屋算法，怎样推出塔数最少？设贪心第 k 座塔中心为 gₖ，任意可覆盖所有房屋的方案按从西到东排序后第 k 座为 aₖ。归纳命题是 aₖ≤gₖ：同样放到第 k 座时，贪心不会更靠西。

完整算法（半径 R）：先按房屋位置从西到东排序；只要还有未覆盖的房屋，取最西边的那间 h，把新塔放在 h+R（道路端点有限时取允许范围内能覆盖 h 的最东点），标记覆盖区间，再继续。输出放置的塔数及位置。这个步骤确保每次既不漏掉 h，又尽量把右侧的新房纳入当前塔。

基例：第一间房在 h，任何方案的首塔若位于 h+R 以东便盖不到 h；贪心放在 h+R，故 a₁≤g₁。归纳：假设 aₖ₋₁≤gₖ₋₁。令 h 是前一贪心塔之后最西边未覆盖的房屋，则 gₖ₋₁+R<h=gₖ−R。若反设 aₖ>gₖ，便有 aₖ₋₁+R≤gₖ₋₁+R<h< aₖ−R；前 k−1 座替代塔到不了 h，第 k 座替代塔从 h 以东才开始覆盖，矛盾。这里 R=5 km 是课件数值；边界上的房屋算已覆盖，所以左边是严格小于。

若贪心共放 r 座，第 r 座照顾的那间房不能由任意 r−1 座合法方案覆盖，故至少需要 r 座。详细图解已放在第二周笔记；这里保留命题与结论，作为后面 greedy stays ahead 的参照。

03 · 磁带存储 I：短文件为何应该先放

这个部分回答什么问题：文件读取必须从磁带开头顺序扫描、每个文件被请求的概率相同，怎样排列才能使平均读取时间最短？若排列后文件长度为 L₁,…,Lₙ，读到第 i 个文件的时间是前缀和 Cᵢ=Σⱼ₌₁ⁱLⱼ，因此 E=(1/n)Σᵢ₌₁ⁿ Cᵢ=(1/n)Σᵢ₌₁ⁿ(n−i+1)Lᵢ。n 是文件数，E 是期望读取时间；该式只适用于等概率请求、顺序扫描且完整读取目标文件的模型。

交换证明：若某个最优排列相邻两项出现 Lᵢ>Lᵢ₊₁，把它们交换，其他前缀与后缀的完成位置不变；缩放后目标 nE 的改变量是旧值减新值 Lᵢ−Lᵢ₊₁>0。这与原排列最优矛盾。因此最优排列没有相邻逆序，长度非递减。实际算法用高效排序，时间 O(n log n)；证明里反复消除逆序并不要求真的用冒泡排序实现。

课件明确建议：真正实现文件排序用 O(n log n) 的 mergesort（归并排序），不要因为证明里交换相邻逆序就写 O(n²) 的冒泡排序。下面用同一组长度演示归并排序的“拆分→有序合并”。

04 · 磁带存储 II：请求概率不同，按什么比值排序

这个部分回答什么问题：文件长短与被请求的概率都不同，先存哪一个？设文件 i 长度 Lᵢ>0、请求概率 pᵢ≥0，Σpᵢ=1。某排列的期望 E=ΣᵢpᵢCᵢ，其中 Cᵢ 是文件 i 在排列中的结束位置。规则是按 pᵢ/Lᵢ 从大到小排序；比值表示每单位扫描长度服务到的请求概率。

证明只看相邻 i、j。原顺序 i 再 j 与交换后 j 再 i 的其他文件贡献相同，旧 E−新 E=Lᵢpⱼ−Lⱼpᵢ。若 pᵢ/Lᵢ<pⱼ/Lⱼ，因长度为正，可交叉相乘得 Lᵢpⱼ>Lⱼpᵢ，交换严格改善期望。故任何最优序列都没有比值逆序。等比值时交换不改变 E，任选顺序。排序 O(n log n)，扫描 O(n)。

05 · 最大延误：最早截止期为何优先

这个部分回答什么问题：只有一台机器、所有任务都必须完成，怎样让最坏的延误尽可能小？任务 i 的处理时长为 lenᵢ、截止期为 dueᵢ，完成时刻为 finᵢ，课件定义有符号 lateness lateᵢ=finᵢ−dueᵢ；目标是最小化 maxᵢ lateᵢ。负数表示提前完成，不能随手改成 max(0,lateᵢ) 而不说明目标改变。任务中间留空只会推迟后续完成，所以存在没有空档的最优安排。

贪心规则是按 due 升序，即 earliest deadline first。证明：在某个最优顺序中找到相邻逆序 i、j，i 先于 j 但 dueᵢ>dueⱼ。设两任务之前的时间为 t。交换后 j 完成于 t+lenⱼ，不晚于原来完成于 t+lenᵢ+lenⱼ；i 交换后完成于 t+lenᵢ+lenⱼ，即原来 j 的完成时刻，但 dueᵢ>dueⱼ，所以新 lateᵢ≤原 lateⱼ。其他任务的完成时刻不变，整体最大延误不会升高。不断消除相邻逆序即可得到截止期排序。

排序花 O(n log n)，扫描计算累计时长与最大延误花 O(n)。若把目标改成平均完成时间、迟交任务数量、总加权延误，须重新求证，不能照搬截止期排序。

06 · 三种最优排序题的同一证明骨架

这个部分回答什么问题：看到排序型贪心题，怎样自己找出规则？先写清目标值对相邻两项的贡献，比较 i→j 和 j→i，消去不变的前后缀；若某种逆序总能交换而不变差，反复消除逆序后就得到排序规则。证明时必须说明交换不破坏可行性，以及整个目标而非某一项的改善。

07 · 最优合并：同一项会被重复付费

这个部分回答什么问题：把 n 个已排序数组两两合并成一个，怎样尽量少搬动元素？合并长度 x、y 的两个数组时，每个元素要移动一次，代价为 x+y；合并后的新数组长度也是 x+y，之后再次合并还会重复付费。把数组长度放入最小优先队列，每次取最短的两个合并，再把和放回队列，直到只剩一个。

把合并过程画成二叉树，原数组是叶子；一个原数组的长度会在从叶到根的每一层合并中付费。因此总成本是 Σᵢ Lᵢ×depth(i)。短数组可以放在较深的位置；对应的安全选择是存在一棵最优合并树，让两棵最轻子树先合并，再缩成一个新权重继续做。这里的完整论证与后面 Huffman 的兄弟交换、缩并归纳同构。

08 · 前缀码：短编码必须仍能唯一解码

这个部分回答什么问题：常见字符能否用短位串节约平均长度，同时保证消息只有一种解码？31 个符号用 5 位固定长度足够，因为 2⁵=32；按每 5 位切分自然无歧义，但高频与低频字符同样长。变长码若随意缩短，会出现某字符码字是另一个的前缀。

前缀码 prefix code 要求任一码字都不是另一码字的前缀。把 0、1 看成二叉树的左右边，所有符号只放在叶子；从根沿位串走，到叶子就确定一个符号，然后从根重新开始。不会在某个符号的叶子继续走向另一符号，因此这种码立即可解且无歧义。反向不成立：非前缀码不一定必然歧义，但课件的例子确实歧义。

优化目标是平均码长 L=Σᵢ fᵢ·len(Cᵢ)，其中 fᵢ 是字符出现概率且总和为 1，Cᵢ 是其码字。例两个符号各 0.5，码字 0 与 1 的平均长为 0.5×1+0.5×1=1 位/符号；要比较的是概率加权长度，而不是最长码字。

09 · Huffman：最轻两棵树反复合并

这个部分回答什么问题：如何构造平均位数最短的前缀码？Huffman 把每个字符作为一棵权重为频率 f 的树；用最小优先队列取出权重最小的两棵树 x、y，新建父结点权重 fₓ+fᵧ，左边记 0、右边记 1，再放回队列。直到只剩根；从根到叶的 0/1 路径就是该字符码字。每轮只做一次局部合并，但其正确性还需后面的最优兄弟性质。

课件的一个合法分支编号得到 a=00、b=01、c=11、d=100、e=101。平均码长 L=0.32×2+0.25×2+0.20×2+0.18×3+0.05×3=2.23 位/符号。左右子树交换会改变具体码字，但不会改变叶深度和平均长度。

10 · Huffman 为什么最优：最深兄弟与缩并

这个部分回答什么问题：为什么可以放心先合并频率最小的两字符？一棵最优前缀码树可以视为满二叉树：若内部结点只有一个孩子，直接删去该结点会缩短其子树码字而不破坏前缀性。满树中取一对最深的兄弟叶；把最低频的两个符号交换到这对叶子上，目标 Σf·depth 不会上升，因为较小频率承担较大的深度更划算。

设最低频为 fₓ、fᵧ。在这样一棵最优树中，把兄弟 x、y 收缩为权重 fₓ+fᵧ 的新叶，得到规模 n−1 的问题；原树的平均码长 = 缩并树的平均码长 + fₓ+fᵧ，因为 x、y 的路径各少一条边。若缩并树不是 n−1 问题的最优树，换成更好的树再展开 x、y，便能改善原树，矛盾。归纳得到每轮最轻两项合并的正确性。

11 · 海啸预警：位置与半径先转成有向关系

课件 p79–80 的七塔图用虚线圆表示每座塔自己能直接广播到的区域，染色帮助观察一轮连锁激活。读图时先看“某塔的圆里有哪些塔”，画从该塔指向那些塔的箭头，再沿箭头继续传。红、蓝、绿只是这个示意的颜色；不能直接把同色点当作同一个 SCC，必须额外检查能否沿箭头返回。g 与其他塔分离，更容易看出它需要独立启动。

这个部分回答什么问题：给部分广播塔安装传感器，使报警沿无线激活关系传到每座塔，传感器最少要几个？塔 i 有位置 (xᵢ,yᵢ) 与半径 rᵢ；若塔 j 到 i 的欧氏距离不超过 rᵢ，就连有向边 i→j。一个装传感器的塔启动后，所有沿有向路径可达的塔最终都会启动。建图时可用 (xᵢ−xⱼ)²+(yᵢ−yⱼ)²≤rᵢ² 判断直接边；例 (0,0)、半径 5 的塔能直接激活 (3,4) 的塔，因为 3²+4²=5²。一般位置下检查所有有序塔对花 O(n²)。

只看半径最大或直接覆盖塔数最多，会忽略多步激活和方向。课件把它们作为待找反例的候选策略。自编的一维可实现例：A 在 x=0、r=2；B 在 x=1、r=1；C 在 x=3、r=2。A、C 的半径和直接覆盖数量都并列最高；若任意破平局先选 A，可激活 A、B，却到不了 C，还需第二个传感器。选 C 会先到 B，B 再到 A，只需一个。此例足以推翻两种“任意破平局都正确”的规则。

正确的结构信号是互相可达：若一组塔内任意两座都能沿路径相互激活，那么这一组只需考虑装一个传感器，并可把整组缩成一座“超级塔”。这就是下一节强连通分量。

12 · SCC：双向可达才是一座“超级塔”

这个部分回答什么问题：如何精确找出可以互相替代的塔群？有向图 G=(V,E) 中，顶点 v 所在的强连通分量 Cᵥ 包含所有同时满足 v⇝u 与 u⇝v 的顶点 u。它是极大集合，不只是某一个环：多个环可共享顶点并合成更大的 SCC。

一次概念上最直接的求法：在原图从 v 做 BFS/DFS，得 Rᵥ（v 能到达的点）；把所有边反向得 Gʳᵉᵛ，在反图从 v 做 BFS/DFS，得 R′ᵥ（原图中能到达 v 的点）；交集 Cᵥ=Rᵥ∩R′ᵥ。课件例子从 e 得 Rₑ={d,e,f,g,h}，R′ₑ={a,b,c,d,e,f}，交集是 {d,e,f}；另两组是 {a,b,c} 与 {g,h}。

若对每个 v 都独立做两次遍历，最坏 O(|V|(|V|+|E|))；这个交集法适合解释定义，计算全部 SCC 应用线性时间的 Tarjan 或 Kosaraju，均为 O(|V|+|E|)。这里 |V|、|E| 分别是顶点、边数。

13 · 线性时间 SCC：Tarjan 的栈与 low 值

这个部分回答什么问题：怎样避免为每个顶点重跑搜索？Tarjan 做一次 DFS，给顶点发现序号 id，维护仍在候选 SCC 栈中的状态，以及 low：从当前 DFS 子树沿已探索的有向边能够回到的、仍在栈中的最早发现序号。子结点返回时用 low[父]=min(low[父],low[子]) 传播；遇到指向栈内顶点的边时用该顶点 id 更新。只有对仍在栈中的目标进行回边更新；已经弹出的 SCC 不应被并入当前 SCC。

Tarjan 操作顺序（补足课件的 sketch）：首次访问 v 时赋 id[v]=low[v]=下一发现序号并压入候选栈；遇未访问的孩子 w 先递归，再令 low[v]=min(low[v],low[w])；遇已访问且仍在候选栈中的 w，令 low[v]=min(low[v],id[w])；已弹栈的 w 不能拿来更新 low。处理完所有出边后若 low[v]=id[v]，从栈顶弹到 v，弹出的就是一个 SCC。若图不连通，对每个尚未访问的点启动 DFS。

当一个 DFS 根 v 满足 low[v]=id[v]，从栈顶弹到 v 的所有顶点组成一个 SCC。每点入栈出栈各一次、每边检查常数次，总 O(|V|+|E|)。另一条课件路线 Kosaraju 做两轮 DFS：用第一轮的完成顺序安排第二轮在反图搜索，同样线性。

Kosaraju 是课件提到的另一条路线，下面把实现步骤补全：在原图 G 对全部顶点做 DFS，记录每点完成时间；构造反图 Gʳᵉᵛ；按原图完成时间从晚到早，在反图对尚未分组的点做 DFS，每次搜索到的一组就是一个 SCC。可直观理解为：第一轮决定从哪些分量开始，反向后跨分量边不能把当前搜索带到尚未处理的分量。两轮 DFS 与反图构造总 O(V+E)。

14 · 凝聚图与最少传感器：数零入度 SCC

这个部分回答什么问题：得到 SCC 之后怎么选传感器？将每个 SCC 缩成一个顶点，若原图有跨 SCC 的边 U→W，就在凝聚图中连边 U→W（重复边只算一次）。凝聚图必是有向无环图 DAG，否则环上的各 SCC 可合并，违反它们的极大性。课件例子缩成 {a,b,c}→{d,e,f}，并且两者可到 {g,h}。

答案是在凝聚图每个入度为 0 的 SCC 中任选一座塔装传感器。下界：零入度 SCC 不能从其他 SCC 激活，因此每个至少要一个。上界：任意 SCC 沿入边不断往前走，在有限 DAG 中必到达某个零入度 SCC；该源点安装的传感器沿有向路径可激活它。所以传感器数恰好等于零入度 SCC 个数。课件例中只有 {a,b,c} 是零入度，因此装一个即可。

算法流程：由坐标与半径建图 → 求全部 SCC → 扫描跨分量边，标记有入边的分量 → 对每个未标记分量选一座塔。若输入已经给了图，后半部分 O(|V|+|E|)；若从 n 座塔的坐标显式建图，检查塔对的 O(n²) 往往主导。不要把“线性图算法”误报成从坐标输入开始的总 O(n)。

15 · 拓扑排序与 Kahn：每轮删除一个零入度点

这个部分回答什么问题：DAG 上如何安排一个尊重所有有向边的处理顺序？拓扑序是顶点排列 σ，使每条 u→v 都满足 σ(u)<σ(v)。DAG 至少有一个拓扑序，可能不唯一；有向环不可能有，因为沿环会要求位置严格递增后又回到起点。

Kahn 算法：预先算每点入度，把所有零入度点放入集合或队列 S；每轮从 S 取一个加入结果 L，视作删去它的出边，并把因此入度变成 0 的邻居加入 S。若输出 |V| 个点，L 是拓扑序；若提前停下但还有顶点，剩余部分含有有向环。初始化和每条边的入度递减各一次，总 O(|V|+|E|)。

可直接照着实现：indegree[v] 先数入边；把所有 indegree=0 的点入队。循环取队首 u，写入输出；对每条 u→v 使 indegree[v] 减 1，刚变成 0 才入队。结束时检查输出数：等于 |V| 就是拓扑序，否则剩余图中有环。边只会在删除其起点时处理一次。

16 · Dijkstra：暂定距离与已定案集合

这个部分回答什么问题：从一个起点 s 到每个顶点的最短路径长度怎么找？课件输入是有向图 G=(V,E)、非负边权 w(e)≥0，并假定 s 可达所有顶点。维护 S：最短距离已证实的顶点集合；d[v]：从 s 到 v、内部顶点只用 S 的已知最短候选路径长度。初始 d[s]=0，其他为 ∞，S 为空。每轮从 V\S 中取 d 最小的 v 加入 S，并检查 v 的出边。

完整迭代：令所有 d=∞、d[s]=0、S=∅；重复取未定案且 d 最小的 v；若最小值已是 ∞，剩余顶点不可达并停止；否则把 v 加入 S，并对每条 v→z 且 z 不在 S 的边做 d[z]←min(d[z],d[v]+w(v,z))。直到所有可达点定案。若要复原最短路，只有严格改善 d[z] 时才记 parent[z]=v。

这里的“不知道”表示暂定距离可能还会下降；一旦顶点进入 S，d[v] 就等于真正的最短距离。例 s→a 权重 4、s→b 权重 1、b→a 权重 2：先看 s 的出边得 d[a]=4、d[b]=1，随后取 b 并更新 d[a]=3。因而不能把第一次发现 a 的路径直接定案。

17 · Dijkstra 的安全选择：第一条离开 S 的边

这个部分回答什么问题：为什么总可以把暂定距离最小的 v 定案？归纳不变式：S 中每点 d 等于真正最短距离；S 外每点 d 是内部顶点只取自 S 的最短候选距离。设本轮选择 v，假如有比 d[v] 更短的 s→v 路径 P，令 y 是 P 上第一个不在 S 的点。P 到 y 的前缀内部顶点全在 S，故前缀长度至少 d[y]。边权非负，所以整条 P 的长度至少这个前缀长度；而贪心选 v 保证 d[v]≤d[y]。于是 P 的长度不可能小于 d[v]，矛盾。

数值感受：若当前 d[v]=4、某条替代路径首次离开 S 时 d[y]=5，那么后续每条边非负，整条替代路径至少 5，不能把 v 的 4 推翻。若后续可以出现权重 −3，则路径可能从 5 降到 2，证明断裂。这里的 4、5、−3 是说明不等式的自编数值，不是课件图上的标号。

18 · 松弛：加入 v 后只检查它的出边

这个部分回答什么问题：v 定案后如何更新候选距离？对每条 v→z，做 relax：d[z]←min(d[z],d[v]+w(v,z))。d[v] 是起点到 v 的已证最短距离，w 是这条边权；如 d[v]=3、边权 4、原 d[z]=10，新 d[z]=min(10,3+4)=7，说明发现了一条更短的已知路径。若旧值 6，则仍保留 6。

为何只看 v 的出边？在加入 v 前已考虑过所有只用旧 S 作内部顶点的路径。若一条新有效候选 s→…→v→…→u→z 的末边来自早已在 S 的 u，那么到 u 的已证最短路径不需要等到 v 加入；把它接上 u→z 的候选在之前就已可用，不会产生新的更小值。因此真正因本轮新出现的改进可以由最后一条 v→z 发现。

19 · Dijkstra 的数据结构：数组与增广堆

这个部分回答什么问题：同一贪心算法为什么会有不同时间复杂度？n=|V|、m=|E|。若 d 放数组，每轮扫描 n 个位置找未定案最小值，共 n 轮 O(n²)；所有出边合计松弛 O(m)，总 O(n²+m)，简单图 m=O(n²) 时写成 O(n²)。稀疏图中反复全表扫描浪费较多。

课件用增广最小堆：堆数组 A[j]=(顶点 i,d[i])，位置数组 P[i]=j，二者保持 A[P[i]] 就是 i 的堆项。最小堆取最小并删除 O(log n)；松弛导致 d[i] 下降时，从 P[i] 直接找到它并上浮 O(log n)。堆交换两项时必须同步更新对应的 P，否则下一次 decrease-key 会改错位置。

建堆按课件保守计 O(n log n)，n 次取最小和至多 m 次成功或尝试松弛各 O(log n)，总 O((n+m)log n)。课件假定 s 可达全图，m≥n−1，可写 O(m log n)。例如 n=5、m=6，数量级由约 11 次对数操作主导；若改用数组则有约 25 次扫描检查，常数与具体实现另算。

20 · MST：最轻跨割边为何安全

这个部分回答什么问题：在连通无向带权图中，怎样选权重和最小的生成树？生成树覆盖全部顶点、无环，恰有 n−1 条边；权重是所选边权之和。设非空真子集 S 与补集 V\S 构成一个割。若跨割边 e 是唯一最轻的，则课件引理说 e 属于每一棵 MST。

反证：若某 MST T 没有 e，把 e 加进 T 会形成唯一环；环上从 e 的 S 端走到 V\S 端的原树路径，必有一条别的跨割边 f。删除 f 后又成生成树；因 w(e)<w(f)，新树更轻，矛盾。例跨割可选边权 3 与 5，若最优树用 5 而没用 3，可交换节省 2。

21 · Kruskal：从森林中只加不成环的边

课件对 Prim 只给出概览：它与 Kruskal 都在逐步建森林，但 Prim 始终维持一个主分量，每次把离当前主分量最近的外部点连进来；下面先用自编图看这个动作，再看课件详讲的 Kruskal。

这个部分回答什么问题：怎样把割引理变成可执行的算法？将所有边按权重升序排序，从 n 个独立顶点开始，依次检查边 (u,v)：若 u、v 已在同一连通分量，加入会形成环，跳过；否则加入并合并两个分量。选到 n−1 条边时得到生成树。Prim 也用贪心，但维持一个不断扩大的主分量；本页聚焦课件详讲的 Kruskal。

安全性：设当前森林 F 中 u 所在分量为 S。被选边 e 跨越 S 与外部；任何比 e 更轻的跨割边若存在，先前已被处理，而且当时也会连接不同分量，不能被跳过。因此 e 是当前割的最轻边。若全图边权互异，它必在每一棵 MST；逐条选完得到唯一 MST。有同权时改用“存在某棵与已选森林兼容的 MST”作不变式。

22 · Union-Find：根代表连通分量

这个部分回答什么问题：如何快速判断一条 Kruskal 候选边是否成环？并查集 Union-Find 将每个当前连通分量表示为一棵有根树，parent 数组存父结点；根的 parent 指向自身或记特殊标记。Find(a) 沿 parent 到根，返回代表元；Find(a)=Find(b) 当且仅当两点已连通。Union(a,b) 先找两根，相同则不动，不同则让一个根指向另一个根。

操作本身：MakeSet(v) 令 parent[v]=v；Find(v) 沿 parent[v]、parent[parent[v]]……走到根；Union(a,b) 先求 ra=Find(a)、rb=Find(b)，若 ra≠rb 才把一个根挂到另一个根。Kruskal 判断 (a,b) 是否成环，正是检查 Find(a)=Find(b)；根的名字无意义，分组关系才重要。

例当前分量 {a,b} 与 {c,d}，若候选边 b→c，Find(b) 与 Find(c) 不同，加入边并 Union；此后 b、c 代表元相同。若再看 a→d，两端根已相同，说明森林中已有一条 a 到 d 的路，再加边就形成环。Find 返回的具体顶点会随 Union 变化，代码只比较是否相等。

若合并时总随意把一棵树挂到另一棵树根下，树高最坏可接近 n；一次 Find、Union 就可能到 O(n)。下一节的按大小合并解决这个高度问题。

23 · 按大小合并：为什么树高至多 log₂ n

这个部分回答什么问题：不用课外的高级并查集优化，也能把 Kruskal 做到什么时间？给每个分量根维护 size，即该分量顶点数。合并两根 c、d 时，把较小分量的根挂到较大分量根下，再更新新根 size；大小相同任选一边。每次一个顶点的深度增加 1，它所在的旧分量至多占合并后新分量的一半；经过 h 次使它变深的合并，所在分量至少扩大到 2ʰ，不能超过 n，因此 h≤log₂n。

按大小合并的具体规则：仅根存有效 size；若 size[ra]<size[rb] 就交换两根，之后令 parent[rb]=ra、size[ra]+=size[rb]。一个顶点的父链深度只有在它处于被挂上的较小一侧时才会增加；此时它所在新分量规模至少翻倍，所以最多增加 ⌊log₂ n⌋ 次。此复杂度分析不需要路径压缩。

Find/Union 每次 O(log n)。Kruskal 对 m 条边排序 O(m log m)=O(m log n)（简单图 m<n²）；之后每条边最多做两次 Find，共 O(m log n)，选 n−1 条边再 Union O(n log n)。连通图 m≥n−1，故总 O(m log n)。例 n=4、m=5，排序 5 条边后最多查 10 次端点根；不要把每次 Find 误算成 O(1)。

24 · 最大间距聚类：Kruskal 在 k 个分量时停下

这个部分回答什么问题：给完整的两两距离图，把点分成 k 组，怎样最大化不同组之间的最小距离？令 spacing(分组)=min{w(u,v):u、v 在不同组}，假定 2≤k≤n。按 Kruskal 升序加边，但在森林恰有 k 个连通分量时停止；这些分量就是输出的 k 组。

完整算法：把完整距离图所有边按权重排序，从 n 个单点分量开始逐条扫描；端点根不同才 Union 并让分量数减 1；一旦分量数等于 k 就停止并输出这些分量。下一条能连接不同分量的最轻边，其权重就是输出分组的 spacing。若 k=n，初始分组已完成，无需选边。

证明：设贪心分组间距为 δ。任意另一种不同的 k 分组，必有一对点 x、y 在贪心中同组，却被另一方案分开。贪心森林中 x 到 y 有路径；这条路径必跨过另一方案某个组的边界，其跨界边权至多 δ，因为贪心合并前用到的边权不超过停止时最小的跨分量边 δ。因此另一方案的间距 ≤δ。若两方案其实划分相同，目标自然相等。

完整图有 m=Θ(n²) 条边；排序 O(m log m)=O(n² log n)，并查集扫描不超过此量。只维护已有的稀疏边集合会改变题目输入和可比较的跨组距离，不能直接照搬完整距离图的结论。

25 · 通用方法、边界与术语回看

这个部分回答什么问题：遇到一题新的贪心或图题，应该先识别哪种证明形状？排序题比较相邻交换的目标差；合并题把总代价写成叶权重×深度；图上选择题先缩出 SCC/DAG 或找到割；最短路题用第一条离开已定案集合的边。这些线索只指向可尝试的方法，具体规则仍需证明。

• 先写明目标：平均读取时间、最大有符号延误、平均码长、传感器数量、路径长度、树总权重和间距不是同一量。
• 把前提列在算法旁：非负边权、固定单源、无向连通图、完整距离图、正长度文件等。
• 把正确性拆为合法性、局部选择的安全性、重复后的终止/最优性；复杂度另算。
• 若找到合法反例，只能否定这一条贪心规则及其声称的适用范围；证明不出来也不等于已经证明不存在任何贪心法。

26 · 自测：先写自己的证明，再展开答案

每题先判断目标、前提与关键不等式，写下理由后再展开答案。答案中的数字例子若标为自编，仅供练习，不作为课堂原题。