CSCI3160 Exercise 5：Kruskal、前缀编码与三元 Huffman

课程：CSCI3160 本组：Regular Exercise Set 5，Problem 1–5；题目（本地课件） p.1；官方答案（本地课件） p.1–3 定位：理解最轻跨边的“存在一棵 MST”保证，掌握 Kruskal 的整体不变量，并将二元 Huffman 的交换与收缩推广到三元。前后：List 4 · 全部练习导航

中文题意是概述，完整英文见原件。本文按原题顺序展开官方思路，并补充其省略的论证。图题假设连通无向；编码题按有限字母表、不同字母不同码字和前缀无歧义理解。码长为根到对应叶子的边数；码字必须非空的边界会单独说明。

Problem 1：多分区中的最轻跨边属于某棵 MST（题目 p.1；答案 p.1）

题意。 将顶点分成若干互不相交的组。端点来自不同组的边称为跨边。证明任一最轻跨边都属于至少一棵 MST。

“某棵”不等于“每棵”

允许边权相同，所以结论只是：对选定的最轻跨边 e，存在一棵包含 e 的 MST。不是说所有 MST 都包含 e，也不是说所有并列最轻跨边可同时装进同一棵树。例如三角形三条边都重 1，三条都是最轻跨边，但一棵生成树只能取其中两条。

完整交换证明

选定最轻跨边 e=u–v，其中 u 属于组 $V_i$ ，v 不属于 $V_i$ 。任取一棵 MST T。如果 T 已含 e，结论直接成立。

否则在 T 中添加 e，产生一个环。沿 e 从 u 走到 v，此时已经离开 $V_i$ ；沿环余下部分继续走，最终要回到 u，因此途中必有另一条边 f 从 $V_i$ 外进入 $V_i$ 。这条 f 也是跨边，并且 f≠e。

由于 e 是所有跨边中最轻者，有 $w(e)\le w(f)$ 。删掉环上的 f，按 List 4 Q3 得到一棵生成树 T′，并且

w(T')=w(T)+w(e)-w(f)\le w(T).

T 已经权重最小，所以 T′ 不可能严格更轻，只能同样最优。T′ 含有 e，证明完毕。

这里不仅说“环中还有一条边”，而是证明“环中还有另一条跨边”，才能把最轻跨边的权重比较用上。

算一遍（自取例子）

三角形 a–b 重 1、b–c 重 2、a–c 重 2；分区是 {a,b} 与 {c}。跨边 a–c、b–c 都重 2。MST {a–b,b–c} 不含 a–c，但把 a–c 加入后删 b–c，得到 {a–b,a–c}，总权重仍为 3。因此 a–c 属于某棵 MST，却不是每棵 MST 都必须选它。

Problem 2：Kruskal 为什么一条条选不会走进死路（题目 p.1；答案 p.1）

题意。 从空边集出发，每次加入不会形成环的最轻边，直到选满 n−1 条，证明最终为 MST。

只知道每条边各自安全还不够

Q1 说每条最轻跨边都属于“某棵”MST。但不同边可能分别属于不同 MST。要证明整个算法，需要更强的不变量：当前所有已选边能同时包含在同一棵 MST 中。

设已选边集为 F。初始为空，任何 MST 都包含它，不变量成立。F 始终无环，可能有多个连通分量，是一片森林。

“不成环”与“跨当前分量”完全等价

若一条边的两端已在 F 的同一连通分量内，它们已有一条路径，加边就成环。若它连接两个不同分量，原先不存在连接两端的路径，加边不会成环。因此算法选的正是当前分量分区下最轻的跨边。

归纳步骤：交换时不能破坏已经选好的边

假设有 MST T 包含 F，下一条选择为 e。若 T 已含 e，不变量继续成立。

若不含，向 T 加 e 成环。按 Q1 的论证，环上有另一条跨 F 分量的边 f。因为 e 是最轻的合法边， $w(e)\le w(f)$ 。换出 f 得到 MST T′。

关键在于 f 不可能是 F 中的已选边：F 的任一边连接的两个顶点必然在同一个 F 分量中，而 f 跨两个不同分量。所以这次交换保留全部 F，同时加入 e。于是 T′ 包含 $F\cup\{e\}$ ，不变量完成归纳。

当 F 有 n−1 条边时，包含它的 MST 也恰有 n−1 条边，二者边集相同，F 本身就是 MST。

算法为什么能选满

如果森林还没连通，原图的连通性保证至少有边跨两个森林分量，否则这些分量之间在原图也无法互达。每次选跨边会合并两个分量，分量数减少 1。从 n 个孤立顶点开始，选 n−1 次后恰剩一个分量。

数字演算（自取例子）

四点 a、b、c、d 的边：a–b 重 1，b–c 重 2，a–c 重 3，c–d 重 4，b–d 重 5。

按权重检查	是否接受	原因
a–b，1	是	合并 a 与 b
b–c，2	是	合并 ab 与 c
a–c，3	否	两端已在 abc，加入会成环
c–d，4	是	合并 abc 与 d，已选满三条

总权重为 7。不是机械地选全图最轻的三条；第三轻边会成环，必须跳过。

实现补充。 把所有边排序，用并查集判断两端是否同分量，能有效实现上述规则。排序 $O(m\log m)$ ；即便只用按大小合并而不依赖复杂的摊还分析，并查集每次查找最坏 $O(\log n)$ ，也可给出总计 $O(m\log m+m\log n+n)$ 的保证。题目本身要求正确性，并未要求最优的数据结构时间界。

Problem 3：前缀码与码树为什么一一对应（题目 p.1；答案 p.1–2）

题意。 二叉码树把字母放在叶子，左右边分别写 0、1，根到叶的位串作为码字。证明这样得到前缀码；反过来，每个前缀码也能构造相应码树。

从树到码：前缀意味着祖先

如果字母 a 的码字是另一个字母 b 的码字的前缀，沿根路径读 b 的码字时，会先完整经过 a 的那条路径，到达 a 的节点，然后再向下走。

这意味着 a 的节点是 b 的祖先。但 a 被放在叶子，叶子没有孩子，不可能再向下走到另一个字母。因此不同字母之间不可能有前缀关系。

还隐含了码字不同：树中给定位串从根出发只有一条确定路径，不会同时到达两个不同叶子。

从码到树：逐位建 trie

从一个空根开始，对每个字母的非空码字依次读每一位。读 0 就沿左孩子走，读 1 就沿右孩子走；缺少对应孩子就创建。读完全部位后，把字母标在当前位置。

创建根 root
对每个字母 a：
    u ← root
    对 a 的码字中每一位 bit：
        若 u 没有 bit 对应的孩子：创建孩子并标记该边
        u ← 该孩子
    在 u 标记字母 a

为什么不会把字母标在内部节点？如果该节点已有更深后代字母，那么当前码字是那个码字的前缀，违反前缀码性质。为什么后来不会经过已有字母节点再向下建？那会说明已有码字是新码字的前缀，同样违反条件。所有建出的路径最终通向某个字母，故没有多余的无标签叶子。

算一遍（本解析自取）

码字为 a=0、b=10、c=11。插入 a 创建根的左叶子；插入 b 创建根的右孩子，再创建它的左叶子；插入 c 复用根到右孩子的第一步，再创建右叶子。

根
├─0→ a
└─1→ 内部节点
       ├─0→ b
       └─1→ c

若再给 d 码字 1，d 会落在已有内部节点；1 是 10、11 的前缀，因此原码集就不满足前缀条件。冲突不是建树算法的意外，而是输入违反定义。

官方伪代码的一处终止条件问题

官方 p.2 写成“重复直到 u 是叶子”，但它初始化为只有一个根的树，根一开始就是叶子，按字面执行会一步也不走。正确循环依据应是码字是否已经读完，如本文伪代码所示，不能以当前节点是否有孩子作为停止条件。

构造总时间为所有码字长度之和，空间也不超过这个量加一个根，因为每读一位至多创建一个节点。前缀共享会减少实际节点数。

非空码字边界。 单个字母放在根上会生成空串，不满足题目要求。若字母表只有一个字母且要求非空码字，可用根加一条边到叶子，码字为 0。因此“任意码树都会给出非空码字”还需要排除根本身就是带字母叶子的单节点树。

Problem 4：最优二叉码树为什么不应有单孩子（题目 p.1；答案 p.2）

题意。 最优码树具有最小平均码长，证明其内部节点都应有两个孩子。

删除没有分支作用的一层

假设内部节点 u 只有一个孩子 v。若 u 不是根，用一条边把 u 的父节点直接连到 v，放在原来通向 u 的左右位置，并删掉 u。若 u 是根，则把 v 直接设为新根。

这样不会改变叶子与字母的对应，也不会破坏“字母只在叶子”的条件，因此仍是前缀码树。u 子树内所有字母的深度都减少 1；其他字母深度不变。码字本身可能改变，但最优编码问题允许改码字，要求保留的是字母和频率。

设每个字母 a 的出现概率为 $p_a$ ，子树叶子集合为 L，平均码长减少

\sum_{a\in L}p_a.

当字母频率都为正时，这个量严格大于 0，和最优性矛盾。所以不能有单孩子内部节点。若“平均”采用等权平均，每个 $p_a=1/n$ ，结论同样成立。

算一遍（自取例子）

a、b、c 的概率为 0.5、0.3、0.2。某树给码 a=00、b=010、c=011，所有字母都先走根唯一的 0 边。码长为 2、3、3，平均 2.5。删掉这条统一前导边后得到 0、10、11，平均 1.5，恰好减少 1。

若只是某个总概率为 0.4 的子树有一层多余单孩子结构，压缩那层平均只减少 0.4，而不是全局减少 1。

必须说明的边界

若字母表只有一个字母且码字必须非空，最优码是一个长度 1 的串，码树的根恰好只有一个孩子；不能删成空码。因此本题结论按通常 至少两个字母 的场景成立。

若允许零频率字母，一个只含零频率字母的单孩子分支压缩后平均值不变，无法证明“每棵最优树都没有这种节点”；只能保证存在压缩后的最优树。严格下降的证明需要该子树有正总频率。区分这两种说法，才能知道交换论证何时给出严格矛盾。

Problem 5：三元 Huffman 为什么每次合并三个最小频率（题目 p.1；答案 p.2–3）

题意。 字母数 n≥3 且为奇数，每个码字使用 0、1、2，要求前缀码的平均长度最短。官方给出“三个最小频率合并”，下面补齐其正确性依据。

目标函数与算法

设字母 a 的频率为 $f_a>0$ ，码长为 $d_a$ 。平均长度是总加权长度除以总频率。分母固定，所以最小化平均长度等价于最小化

C(T)=\sum_a f_a d_a.

频率也可以已归一为概率。若有零频率，可理解为保留零频率叶子；下面严格改进处改为“不增加”，选取结构最简的最优树，算法仍可采用。

为每个字母创建一个叶子，以频率为权重加入最小优先队列
当队列中节点数大于 1：
    取出权重最小的三个根 a、b、c
    创建新父节点 z，令三个孩子为 a、b、c
    三条边标 0、1、2
    z 的权重 ← a、b、c 的权重之和
    将 z 放回优先队列
剩下的根就是码树根
沿树输出每个字母的根到叶码字

每次取三放一，节点根数减少 2。从奇数 n 开始，依次为 n、n−2、…、3、1，不会在最后卡在 2。这解释算法为什么要求奇数；不过光解释程序能运行，还没有证明最优性。

第一步：为什么奇数叶子时可以只考虑满三叉树

一般三元前缀码的 trie 允许内部节点有 1、2、3 个孩子。单孩子可像 Q4 那样压缩，不增加码长。剩下只考虑二孩子与三孩子内部节点。

设二孩子节点数为 b，三孩子节点数为 t，叶子数为 n。全树节点数为 $n+b+t$ ，所以边数为 $n+b+t-1$ ；按每个内部节点的孩子数数边，又是 $2b+3t$ 。相等得到

n=1+b+2t.

n 为奇数意味着 b 为偶数。若存在二孩子节点，就至少有两个，称为 u、v，并令 u 的深度不大于 v。

把 v 的一个孩子子树取出，接成 u 的第三个孩子；原先 v 剩一个孩子，再把 v 压缩掉。被移动的子树原来从深度 $d(v)+1$ 开始，现在从 $d(u)+1$ 开始，深度不增加；v 剩余的孩子子树上移一层，其他叶子不变。即使 u 是 v 的祖先，这个操作也合法：移动的是 v 的后代到祖先的空余孩子位置，不会产生环。

因此总代价不增加，且二孩子节点减少两个。反复操作，最终得到同样好或更好的、每个内部节点都有三个孩子的树。对正频率最优树，原来的那种二孩子结构还会导致严格改善；对含零频率的情况，只需“存在满三叉最优树”即可。

这一步很重要：不能仅凭“三元码用三个符号”就断言每个内部节点必须有三个孩子。

第二步：三个最小频率可以放在最深处作兄弟

在满三叉树中选一个深度最大的内部节点。它的三个孩子都必须是叶子，否则还存在更深的内部节点。因此得到三个同深度、且深度为全树最大值的兄弟叶子。

设某个较小频率 a 位于较浅深度 $d_a$ ，较大频率 b 位于更深的 $d_b$ ，其中 $f_a\le f_b$ 、 $d_a\le d_b$ 。交换它们的叶子标签，代价变化为

\begin{aligned} C_{\mathrm{new}}-C_{\mathrm{old}} &=f_a d_b+f_b d_a-f_a d_a-f_b d_b\\ &=(f_a-f_b)(d_b-d_a)\le0. \end{aligned}

所以小频率放得更深不会更差。把三个最小频率字母依次交换到上述三个最深兄弟位置，可保证代价不增加，已经放好的最小字母不再换出。于是存在一个最优树，让三个最小频率成为兄弟。这正是贪心第一步需要的安全性。

第三步：把三个兄弟收缩成一个伪字母

设三个最小频率字母为 a、b、c，它们的共同父节点深度为 d。原来三个贡献之和为

(f_a+f_b+f_c)(d+1).

用频率 $f_z=f_a+f_b+f_c$ 的伪字母 z 替换它们的父节点，收缩后贡献为 $f_zd$ 。因此有准确关系

C(T)=C(T_{\mathrm{reduced}})+f_a+f_b+f_c.

增加的部分只是固定常数。若收缩后的树不是缩小问题的最优解，就可以换成更好的缩小树，再把 z 展开为 a、b、c，原问题也会变得更好，与原来最优矛盾。因此缩小问题具有最优子结构。

缩小后字母数为 n−2，仍是奇数。递归应用同样论证，直到只剩一个伪字母；它在收缩问题里允许占根，展开后原始 n≥3 个字母的码字都非空。贪心安全加上收缩最优性，完成整个算法的归纳证明。

把一个完整例子算到底（本解析自取）

五个字母 a、b、c、d、e 的频率分别为 1、2、3、4、5，总频率 15。

取 1、2、3 合并为伪节点 z，权重 6。剩余队列为 4、5、6。
将 4、5、6 合并为根，权重 15。
可给 d 码 0，e 码 1，伪节点 z 的前缀为 2；z 内部再给 a、b、c 分别接 0、1、2，因此它们码字为 20、21、22。

码长是 2、2、2、1、1，加权长度为

1\cdot2+2\cdot2+3\cdot2+4\cdot1+5\cdot1=21,

平均长度为 $21/15=1.4$ 个三元符号。也可把两次合并权重相加， $6+15=21$ ；每次合并恰使其所有后代叶子深度加一，所以这个验算成立。

若把频率 3、4、5 的字母放入深层分支，加权长度会是 $1+2+2(3+4+5)=27$ ，明显更差。频率大的字母应尽量浅，合并小频率正是在为这一点保留空间。

补充：三元码长度单位与二进制文件大小不同。 上例的1.4是每个原字母平均使用1.4个三元符号，不是1.4比特。三元边标签可以是0、1、2；若真正存入二进制文件，还需说明如何编码这些标签，不能把不同字母表的单位直接比较。

自测：偶数字母数时，直接每次取三个会在哪一步失败？

自取4个字母，取三放一后只剩2个根，下一次取三个不合法。这说明前面的奇数条件不是装饰。若研究偶数情形，可加一个零频率虚叶使总数变奇数，再用满三叉构造；这是额外推广，需要说明虚叶不对应真实输入符号，不能把它当作原题已经要求输出的字母。

为什么加零叶不该被解释成“多一种真实字母”？

它只是补齐树形结构，不增加真实文本出现概率；最终编码表只提供给原字母。若将虚叶计作正频率，优化目标和合并选择就变了。

时间、空间和输出规模

用最小堆建队列为 $O(n)$ ；一共 $(n-1)/2$ 次合并，每次常数次堆操作，花 $O(\log n)$ ，建树总时间 $O(n\log n)$ 。满三叉树内部节点数为 $(n-1)/2$ ，总节点数线性，所以树和队列空间 $O(n)$ 。

若必须显式列出每个字母的全部码串，还应加上输出总码长 L 的代价，整体为 $O(n\log n+L)$ 。不能忽略长码串的实际输出工作。用树作为紧凑表示时，建树本身就是前面的界。

易错点。 合并后必须把频率和放回队列，让它参与后续最小值选择；不能只把原字母一次排序后固定每三个一组。三个孩子的 0、1、2 顺序不影响长度和代价。二元 Huffman 的“合并两个”不能直接保留，因为每次合并必须与编码字母表的分支数匹配。

本讲核心考点

Q1：最轻跨边保证属于某棵 MST，允许并列权重。
Q2：所有已选边同时包含在某棵 MST 中，交换不能删掉既有选择。
Q3：前缀关系对应祖先关系；建 trie 按码字位数停止。
Q4：单孩子压缩减少平均码长，非空码与零频率有边界。
Q5：满三叉结构、三最小兄弟交换、收缩代价恒等式共同证明最优。

来源与证据

官方题目 p.1；官方答案 p.1–3，2026-09-30 下载。
官方 Q5 仅提示推广课堂证明；本文补全满三叉树存在性、交换、收缩归纳及输出规模分析。
官方 Q3 建树循环按字面不能处理初始单根，本文明确更正为逐位遍历。
考试证据：本次仅核对官方练习与答案，未据此断言考试范围。