CSCI3160 Exercise 4：树、可寻址优先队列与最小生成树

课程：CSCI3160 本组：Regular Exercise Set 4，Problem 1–6；题目（本地课件） p.1；官方答案（本地课件） p.1–3 定位：补齐树的交换性质，解释按编号删除的数据结构，再把这些工具用于 MST 唯一性和 Prim 的实现。 前后：List 3 · List 5

以下题意为中文概述，英文全文见原件。除特别说明，图是有限无向简单图，树非空；讨论 MST 时图需连通。复杂度按课程 RAM 模型计算。本文补充的例子、边界条件和证明展开不冒充官方原话。

Problem 1：树为什么有叶子、为什么边数少一（题目 p.1；答案 p.1）

题意。 证明树存在度为 1 的顶点，并证明有 n 个顶点的树恰有 n−1 条边。

先修正单顶点边界

若 n=1，树只有一个顶点，度为 0，不存在度为 1 的叶子。因此第一条应限定 n≥2；第二条 n=1 时仍正确，因为边数为 0。官方归纳从 n=2 开始，未单独说明这个前提。

最长简单路径的端点一定是叶子

简单路径不重复顶点。在一棵至少两个顶点的树中，取一条顶点数最多的简单路径，设某端点为 u，它在路径上的相邻点为 v。

如果 u 还有一个不同于 v 的邻居 w，有两种可能：w 不在当前路径上，则可把 w 接到端点，得到更长简单路径，与最长性矛盾；w 已在当前路径上，则边 u–w 加上路径中 u 到 w 的一段构成环，与树无环矛盾。

因此 u 只能与 v 相邻，度为 1。另一个端点同理，所以实际上 n≥2 的树至少有两个叶子；本题只要求至少一个。

用删叶子归纳边数

以 n=1 为基例，边数 0=n−1。对 n≥2 的树，找一个叶子 u，删掉它和唯一相邻边。剩余图仍无环，因为删边不可能创造环；剩余图也连通，因为连接其他两个顶点的简单路径不可能把度为 1 的 u 当作内部顶点，所以这些路径没被破坏。

因此剩余图是 n−1 个顶点的树。由归纳假设，它有 n−2 条边。将删掉的一条边加回去，原树共有 n−1 条边。

算一遍（自取例子）。 路径 a—b—c—d 有 4 个顶点和 3 条边。删叶子 d 后剩 3 点 2 边，再删 a 后剩 2 点 1 边。每次顶点数与边数同步减少一，直到 1 点 0 边。

易错点。 不能只说“删一个顶点后还是树”：删内部顶点可能断开图。必须用叶子，并说明剩余图为什么仍连通。

Problem 2：连通加 n−1 条边为什么足够（题目 p.1；答案 p.1）

题意。 简单图有 n 个顶点、n−1 条边且连通，证明它是树。

为什么连通图一定有生成树

可从任意顶点执行 DFS 或 BFS：每次首次发现一个新顶点时，记录让它首次被发现的那条边。连通保证所有顶点最终被发现；除起点外，每个顶点恰好贡献一条发现边，因此共 n−1 条。记录边连通所有顶点且不会有环：每条新边都是把一个尚未加入的顶点接进已有结构。这就是生成树 T。

因为 T 是原图 G 的子图，又由 Q1 知它已经有 n−1 条边，恰好耗尽 G 的全部边，所以 G=T，G 就是树。

两个条件都不可丢

只有 n−1 条边不够。例如自取的四顶点图，三个顶点构成三角形，第四个孤立，共 3 条边，却有环而不连通。只有连通也不够：三角形连通但有环。因此必须把边数与连通性合起来使用。

这是后面交换论证的快捷工具：只要证明换边后仍连通，并核对边数仍为 n−1，就不必另外从头证明无环。

Problem 3：加一条边，再删环上一条边，仍是一棵树（题目 p.1；答案 p.1）

题意。 在树上新增一条连接原有顶点的边，形成环；再删去该环中的任意一条边，证明剩余图还是树。

新边为什么恰好产生一个环

树中任意两顶点之间有唯一简单路径。存在性来自连通；若有两条不同简单路径，它们从某处分叉后再次汇合，就会形成环，违反无环。

新增边 e 连接 u、v，它和原树中唯一的 u 到 v 路径构成一个环。任何新环都必须用 e，因为旧树无环；而使用 e 的环余下部分必须是旧树中 u 到 v 的路径，所以这个环唯一。

删掉环上边不会失去连通性

设被删边是 a–b。环中还有另一条绕行路线从 a 到 b，完全不经过被删边。所以旧图中任何使用 a–b 的连接，都可以改成沿环另一侧绕行。替换后可能是一条重复顶点的游走，但去掉重复闭合段即可得到路径；因此“仍可连接”成立。

边数方面，原树 n−1 条，加一减一后仍为 n−1；顶点数不变。由 Q2，连通且边数为 n−1 的图是树。

算一遍（自取例子）

树为 a—b—c—d，新增 a–c，产生三角环 a–b–c–a。删 b–c 后，仍可从 b 经 a、c 到 d，剩余 3 条边连接 4 点，是树。

如果误删不在环上的 c–d，d 就会孤立，三角环还留着。所以“任意删一条”不成立，必须删环上的边。若删回刚添加的边，也合法，只是回到原树。

Problem 4：按 id 删除，同时按 key 取最小值（题目 p.1；答案 p.2）

题意。 保存唯一 id 与整数 key 的配对，支持插入、按 id 删除、删除并返回最小 key 的记录；要求线性空间，每次操作对数时间。

为什么一个普通最小堆还不够

最小堆擅长按 key 取最小，却不能直接根据任意 id 找到记录位置。若每次按 id 扫描整个堆，删除就变成线性。两个查询方向需要两个索引。

官方方案是两棵搜索树，但为了满足最坏 $O(\log n)$，必须明确使用 平衡二叉搜索树，例如 AVL 或红黑树。普通不平衡 BST 遇到有序插入可退化成链，不能保证本题要求。

两棵树的排序键要写准确

• 第一棵树按 id 排序，节点保存 (id,key)。
• 第二棵树按二元键 (key,id) 的字典序排序，节点同样能找到完整记录。

为什么第二棵不能只用 key 当唯一索引？题目只保证 id 不重复，允许两条记录有相同 key。附加 id 后二元键唯一，同时排序首字段仍是 key，不影响寻找最小值。

Insert(id,key)：
    在按 id 的树中插入该记录
    在按 (key,id) 的树中插入该记录

Delete(id)：
    在第一棵树中查找 id
    若不存在：结束
    读出该记录的 key
    从两棵树中分别删除 id 和 (key,id)

DeleteMin：
    若集合为空：返回空标记
    在第二棵树中找到最左节点，读出 (key,id)
    从两棵树中分别删除对应节点
    返回 (id,key)

始终维护不变量：两棵树包含完全相同的一组记录，只是索引次序不同。任一删除都要同步更新两棵树，否则下次查找可能读到已删除对象。

补充：一次改键实际涉及两个索引。 假设 id=7 的 key 从4变成2。按id的树仍以7定位，但记录内容要改成2；按(key,id)的树则必须删除旧键(4,7)、插入新键(2,7)。只在旧节点内改数字，不恢复第二棵树的排序位置，会破坏“最左节点就是最小key”的不变量。

算一遍（自取例子）

插入 (7,4)、(2,4)、(9,1)。第一棵按 id 的次序是 2、7、9；第二棵按 (key,id) 的次序是 (1,9)、(4,2)、(4,7)。

Delete(7) 先查出 key=4，再删除第二棵中的 (4,7)，不会误删同 key 的 id=2。随后 DeleteMin 取出 (9,1)，两棵树都只剩 (2,4)。

每次操作只做常数次平衡树查找、插入或删除，每次最坏 $O(\log n)$，故总计仍为对数。每条记录只存常数份索引节点，空间 $O(n)$。空集合与单元素时用 $O(\log(n+1))$ 可避免对数零的记号问题。

补充。 也可用可寻址堆加 id 到位置的索引，但若索引用普通哈希表，需要区分期望保证与最坏保证。本题的两棵平衡树方案无需这种额外假设。

Problem 5：所有边权互异为什么使 MST 唯一（题目 p.1；答案 p.2）

题意。 在边权两两不同的连通无向图中，证明最小生成树唯一。

先明确要否定的是什么

“每条边权不同”不意味着“任何两个边集合的总权重不同”，例如不同整数也可能组合出相同和。唯一性必须使用生成树结构，不能仅凭总和直觉。

用最轻的差异边作交换

反设有两棵不同的 MST，称为 T 和 U。在只属于其中一棵的所有边中，选权重最小的 e；交换两棵树名称后，可设 e 在 T 中却不在 U 中。

将 e 加入 U，产生唯一环 C。C 上必有一条边 f 不在 T 中；否则 C 上所有边连同 e 都在 T 中，T 就含环。因为 C 中除 e 外的边来自 U，所以 f 属于 U 而不属于 T，也是一条差异边。

e 是最轻差异边，又因为边权互异且 f≠e，所以 $w(e)<w(f)$。由 Q3，换掉 f 得到的新图 $U'=U+e-f$ 仍是生成树；其总权重为

这与 U 已是最小生成树矛盾。因此不可能有两棵不同 MST。

数字帮助理解严格不等号（自取例子）

假设某次合法交换加入权重 3 的边、删去权重 7 的边，总权重就下降 4；这才产生“原树不最优”的矛盾。如果两条边都重 3，交换后只会得到另一棵等重树，没有矛盾。所以不同权重的作用在于把“不更重”加强成“严格更轻”。

三角形三条边全重 1，就确实有三棵等重 MST。反过来，含重复权重的图也可能有唯一 MST，例如原图本身就是一棵树。因此互异是充分条件，不是必要条件。

与官方证明的关系。 官方使用 Prim 的第一条分歧边来交换，也是在利用某个割上唯一最轻边。本文使用对称差中的最轻边，可统一处理，无需按 Prim 的第一步和后续步骤分情况。

Problem 6：Prim 怎样实现目标时间界（题目 p.1；答案 p.2–3）

题意。 实现 Prim，使运行时间达到顶点数加边数乘以顶点数对数。

每个树外顶点只维护一条“当前最好连接”

令 S 为已进入树的顶点集合。对每个树外顶点 v，维护：

• key[v]：从 S 到 v 的所有边中的最小权重；暂时没有边则为正无穷。
• parent[v]：实现该最小权重的树内顶点。
• inTree[v]：是否已在 S 中，以数组支持常数时间判断。

优先队列按 key 排序，支持按顶点 id 修改 key 和取最小。可用 Q4 的两索引结构；每次降低 key，删除旧记录再插入新记录，总时间仍为 $O(\log n)$。使用二叉堆时则要维护顶点到堆位置的索引，不能线性搜索位置。

为什么取最小 key 就是在取最轻跨割边

每个树外顶点的 key 已经是以它为外侧端点的最轻跨边。再对所有树外顶点取最小，相当于对所有跨边取最小。这个最轻跨割边是 Prim 的安全选择，而不是求从根开始的最短路径。

伪代码：从单个根开始的标准版本

任选根 r
所有 key 设为正无穷，parent 设为空；key[r] ← 0
将全部顶点放入可按 id 更新的最小优先队列
S ← 空集合；答案边集 ← 空集合
当队列非空：
    u ← DeleteMin()
    若 key[u] 为正无穷：报告图不连通，无法得到一棵生成树
    将 u 加入 S，inTree[u] ← 真
    若 parent[u] 非空：把边 (parent[u],u) 加入答案
    对 u 的邻接表中每条边 (u,v)，权重为 w：
        若 v 不在 S 且 w < key[v]：
            key[v] ← w；parent[v] ← u
            在队列中更新 v 的 key
返回答案边集

无向图的每条边在两个端点邻接表中各出现一次。必须使用邻接表，不能每次扫描整个邻接矩阵再声称边扫描总量是线性的。

为什么只需看新顶点的邻接边

加入 u 后，对任何尚在树外的 v，原先从 S 到 v 的边并未消失，新增可能性只有 u–v。因此把旧 key[v] 与新边权取最小就够了，不需要重新扫描整个已选集合。父节点必须与 key 同步更新，否则权重对了却可能恢复出错误边集。

算一遍（自取连通图）

边为 a–b 重 4、a–c 重 1、b–c 重 2、b–d 重 1、c–d 重 5。从 a 开始：

得到总权重 4。注意 d 的 key 最终是 1，不是从 a 沿树走到 d 的距离 4；Prim 的 key 表示“一条连接边”，不是距离累加值。这是与 Dijkstra 最容易混淆的地方。

操作次数逐项相加

设 n 为顶点数、m 为边数。插入 n 个顶点至多 $O(n\log n)$；DeleteMin 共 n 次，$O(n\log n)$；邻接表检查总共 2m 次，$O(m)$；每次边检查至多引发一次 key 更新，更新总共至多 2m 次，每次 $O(\log n)$。因此

除存图所需 $O(n+m)$ 空间，队列和辅助数组是 $O(n)$。单顶点单独处理即可；严格统一可把对数写为 $\log(n+1)$。

官方版本。 官方先选全图最轻边及其两端作初始 S，再维护同样的 key。初始化不同，但后面的不变量和操作计数一致。本文单根版本免去单顶点图没有初始边的例外。

本讲核心考点

• Q1：最长路径端点给叶子，删叶子归纳边数；单顶点要另说。
• Q2：连通图包含生成树，结合边数即得相等。
• Q3：环边可绕行，交换保持生成树。
• Q4：最坏对数需要平衡树，重复 key 要用 id 消歧。
• Q5：交换中的严格降权矛盾证明唯一性。
• Q6：最轻跨边不变量、按 id 更新和邻接表共同实现时间界。

来源与证据

• 官方题目 p.1；官方答案 p.1–3，2026-09-30 下载。
• 本文补充单顶点与连通性前提、平衡性和重复 key 处理，并给出等价的 MST 唯一性证明及单根 Prim 实现。
• 考试证据：本次仅核对官方练习与答案，未据此断言考试范围。