Vince Jiang

CSCI3160 / 辅导 · 本站更新

CSCI3160 T05 · Part 2/2 Kruskal正确性

课程：CSCI3160 Design and Analysis of Algorithms 本讲：T05，第 2 部分 / 共 2 部分 · 原件 T05-Kruskal算法-未核-隐藏.pdf（本地课件） p.14–20 定位：以整个已选前缀为不变量，完成换边证明并分析排序与并查集成本。 前后：上一份 Part 1

p.14–15：不变式要包含整个前缀【新】

p.14 设ei为第i条选择，归纳证明每个前缀都包含于某棵MST。p.15 若已有MST T包含前i−1条且也含ei，直接完成这一步；否则做交换。逐边分别“属于某棵MST”不够，因为那些MST可能互不相同。

基例也应写全：e1 是全图最轻边，任选一棵 MST T。若 e1 已在 T 中即完成；否则加入 e1 得唯一环，删去环上任一不同边 e′，由于 w(e1)≤w(e′)w(e_1)\le w(e')，新生成树成本不增，所以也是 MST 且含 e1。单顶点无边时直接返回即可，不必执行这个基例。

p.16–18：找到不会删掉旧选择的替换边

p.16 已选森林G′只含前i−1条边；p.17 把ei={u,v}加入T形成唯一环，u、v位于G′的不同分量。p.18 沿环从u经ei到v，再返回u所在分量，必跨过另一条跨边e′。ei是当时最轻跨边，所以w(ei)≤w(e′)；e′连接不同G′分量，因此不是已选前缀中的边。

图（p.17–18）：左图T加虚线ei成环，右图G′显示分量。元素：e′在返回u所在分量的边界上。看什么：删e′既断环，又不会破坏原来承诺保留的前i−1条选择。

补充：为什么“每条边分别安全”还不够。 自取三角形三条边权都为1。每条边单独都属于某棵MST，但三条一起构成环，不可能同时属于任何生成树。所以归纳假设必须承诺一个共同的最优树包含当前全部前缀，而不是为每条边各找一棵不同的树。

交换时不能删旧前缀还有实现含义：已经作出的贪心决策不会被算法回滚。证明可以更换作为见证的最优树，但不能更换实际已选边。新的 e′ 跨当前森林分量，旧前缀边则都在某个分量内部，两者身份不可能重合，因而保护了所有旧决策。

自测：如果 e 与 e′ 同权，证明是否失败？

不失败。只需要新树成本不增；相等时得到另一棵同样最优的树。要证明某边属于每棵MST才需要更强的严格条件。课堂算法允许并列任选，证明也必须允许这种非唯一性。

p.19–20：交换完成，再核算时间

p.19 用T−e′+ei得到生成树，成本不增；T本来最优，故新树同样最优，并保留前i条。到V−1条时已选树本身就是MST。p.20 给实现界O(Elog E)。补充实现：先排序边，用并查集判断两端根是否相同，不同才合并。按秩合并的树高O(log V)，每边两次Find，连通简单图下log V=O(log E)，排序和查集合计满足界；路径压缩还能改善并查集部分，但本界并不要求展开其高级分析。

交换的成本账本为 w(T′)=w(T)−w(e′)+w(ei)≤w(T)w(T')=w(T)-w(e')+w(e_i)\le w(T)；另一方面 MST 最优性给出 w(T′)≥w(T)w(T')\ge w(T)，故只能相等。归纳走到 |V|−1 条后，它们本身已经构成生成树；包含相同数量边的见证 MST 不可能再多别的边。

完整实现只需“排序全部边→每点 MakeSet→顺序扫描边→Find 不同时记录此边并 Union→记录满 |V|−1 条即停止”。原页实现细节作为练习，这里补齐以便独立学习。

本辅导新算法保留在辅导正文，不自动新增到主课记忆条目。

本讲核心考点

  • 不变式是全部已选边同时包含在某棵MST中（p.14–20；C 级）。
  • 交换边必须跨当前分量，从而不删掉先前已选边（p.16–19；C 级）。

附录

本部分所需过程已在正文展开。

来源与证据

  • 本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。

  • 原件：T05-Kruskal算法-未核-隐藏.pdf（本地课件），本部分 p.14–20；页码均为 PDF 页号。

  • 版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。

  • 发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。

  • 既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无

  • 缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。