CSCI3160 T04 Prim实现

课程：CSCI3160 Design and Analysis of Algorithms 本讲：T04 Prim实现 · 原件 T04-Prim实现-未核-隐藏.pdf（本地课件） p.1–38 定位：以每个树外点的最轻跨边为键，用优先队列维护 Prim。 承接：L04 最小生成树

p.1–3：需要优化的是实现【新】

p.1 目标为 $O((V+E)\log V)$ 实现；p.2 定义生成树覆盖全部顶点、边来自原连通无向图、总代价为边权和。图（p.3）：同一个八点图的三棵生成树。元素：前两棵权37，第三棵48。看什么：生成树满足连通无环还不够，MST另需最小总权；同权最优树可能不唯一。

后续八点例图的完整边权为 ab=1、ac=3、bc=3、af=7、ah=8、bg=13、be=10、cf=5、ch=6、ef=2、ed=12、gh=9、gd=11。未列点对没有边；交叉线不是新顶点。

p.3 三棵树可用边集合完整复现：第一棵 {ab,bc,cf,ef,ch,gh,gd}，权和 1+3+5+2+6+9+11=37；第二棵把 bc 换成 ac，同为37；第三棵 {ac,bc,bg,ah,af,ef,ed}，权和 3+3+13+8+7+2+12=48。它们都有8个点、7条边且连通，前两棵成本相同但边不同。

p.4–6：树内与树外

p.4 逐次将一个顶点纳入S，跨边连接S与V\S。原句“in V and ... V\S”首个V按上下文应为S。p.5 展示原图，p.6 用蓝虚线圈出a,b,c。加入已在S的点会成环，算法只从跨边引入新点。

p.7–9：每点一个候选足够

p.7 标明其余点在绿色区域，p.8 红线标跨边，p.9 为每个树外v保存最轻跨边best-cross(v)。

p.9 “the lightest cross edge”

任何跨边都有唯一树外端点；该点的最佳跨边不更重，因此所有best-cross中的最小者就是全局最轻跨边。无需在每轮重新扫描所有边找最小。

p.10–12：初始化不变式

p.10 从全图最轻边ab开始，S={a,b}；对树外点在接a与接b的边中选轻者，不存在的候选视为无穷。p.11 初表为c:ac3，d:空∞，e:be10，f:af7，g:bg13，h:ah8。p.12 每轮取最小候选边，加入其树外端点v，只检查v的邻边更新其余候选。

p.13–15：加入 c，再取 f

p.13 取ac3，S增加c。p.14 扫c邻边，f由af7改cf5，h由ah8改ch6，c从候选表删除；p.15 最小为cf5，加入f。相同3权的bc也可以选，得到不同的合法MST。

p.16–18：更轻候选出现后会插到前面

p.16 新点f使e从be10改ef2。p.17 下一条选ef2，虽然它比刚选的5还小；Prim选边权不要求单调增加。p.18 e使d从无穷变ed12。

p.19–21：逐步接入内部顶点

p.19 选ch6加入h，p.20 g从bg13变gh9，p.21 选gh9加入g。每次更新只比较一条新跨边与旧最佳，不删除仍合法的其他候选。

p.22–24：最后连接 d

p.22 g使d从ed12变gd11；p.23 取gd11，p.24 全部八点已入树。七条树边ab1、ac3、cf5、ef2、ch6、gh9、gd11相加37。图（p.24）：红边形成该树，原图未选边仍画为黑线。看什么：红边数7，连通八点，不需要把图中全部可见线都计入总代价。

p.25–27：数据结构需要按两种键访问

p.25 元组(id,weight,data)支持Find、Insert、Delete、DeleteMin，每项O(log V)、空间O(V)。补充实现：带id位置映射的二叉堆，或按id和(weight,id)各建一棵平衡树并同步维护；普通只有最小堆的结构并不能凭id直接O(log V)找到元素。

四个操作的语义分别是：Find(t) 按 id=t 找元组，不存在则返回空；Insert 加一个新元组；Delete(t) 按 id 删除；DeleteMin 按 weight 取走最小元组。id 必须唯一，weight 可以并列；实现可用 id 打破同权顺序，并列不会破坏 Prim 正确性。

p.26 为六个树外点插入元组，总O(Vlog V)；p.27 DeleteMin取c的元组，O(log V)。元组data存最佳边，weight存该边权，而不是从起点到v的路径和。

把 p.11–24 和 p.26–38 两次演示的所有队列状态合在一张表；表中“点:父边/权重”已足以恢复完整的 (id,weight,data) 元组。

“取出”页与紧随的“恢复不变式”页之间，恰是删除所取点的元组、再做邻边更新。状态表保留所有未变化候选，读者可按完整边表逐项验证。

p.28–30：把更新拆为查、删、插

p.28 扫c邻边，a、b已无元组故跳过，f、h各查到旧权后删除旧元组、插入新元组，总O(deg(c)log V)。p.29 DeleteMin取f；p.30 e由10改2。p.30文字把“查到旧weight”写为2，但紧随其后的删除为10，按表和操作应读旧值10、新值2。

p.31–33：无穷也要作为键处理

p.31 取e，p.32 d由∞改12；p.33 取h。无穷候选表示暂时没有跨边，连通性保证S未满时至少存在有限候选。若推广到非连通图，取到无穷应报告无法生成单棵生成树或开始新分量，不能把空边加入树。

p.34–36：更新元组的 id 不能换成新父点

p.34 g由13改9，p.35 取g，p.36 d由12改11。该页末句误写insert(g,11,{g,d})，正确是insert(d,11,{g,d})：候选属于尚在树外的d，g已经被移出队列。否则会重新插入已处理点并丢失d的记录。

补充：新点加入时，候选为何只会变轻。 旧 best-cross(v) 是从旧 S 到 v 的最轻边。加入 u 后，新候选集合恰是旧候选再加可能的 uv；所以新值为 min(旧值,w(u,v))，其余旧候选都仍合法，不需要从零重算。u 自己的队列记录必须先删除，因为它已不再是树外点。

以原例加入 c 为一次完整操作：先删除 id=c；扫描到 a、b 时发现二者已在树内，跳过；f 的键从7降5、父边改成cf；h从8降6、父边改成ch；其余候选不变。若只改数字却不改 data，最后会按新权计成本、按旧边建树，两者不一致。

p.37–38：对度数求和

p.37 最后取d；p.38 总时间为初始化O(Vlog V)、V次取最小O(Vlog V)、邻边检查与更新 $O(\sum_v deg(v)\log V)$。无向图度数和2E，故总 $O((V+E)\log V)$，图存储O(V+E)、队列额外O(V)。不能把每个点都粗估扫描全部E条边而错算VElog V。

本讲核心考点

• （C 级 通识）best-cross不变式与“每点一个候选”为什么足够。
• （C 级 通识）手动执行优先队列的删除与更新。
• （C 级 通识）以度数和2E核算总时间。

附录

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

来源与证据

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

• 原件：T04-Prim实现-未核-隐藏.pdf（本地课件）；页码均为 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：无

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