知识卡片
Prim维护到整棵树的候选边
设S为已入树顶点。每个未入树v的key记录已知从S接到v的最小边权,parent记录该边在S中的端点;选全体白色顶点中key最小者加入S,再用其邻边尝试改善外部key。
只在v未入树且w(u,v)[v]时更新,不能无条件覆盖已有更好候选,也不是比较v.key是否小于u.key。原文部分叙述混淆这两个比较,后续源码实际比较边权与候选键。
图例由a开始,依次选c、b、d,再f、e,最终选边a-c=4、c-b=6、b-d=2、b-f=4、f-e=1,总17。b的候选来自此前c,而不是限定与刚选d最近。贪心依据是当前割的最轻跨边可以安全扩展某棵最优树,平权不要求唯一选择。
297与293对照:Prim的key是从当前树连接到顶点的一条最小边权;Dijkstra的d是从源出发的累计路径估计。两者都选最小候选,但更新公式及非负边前提不能互换。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
键值最小的顶点u。开始,此顶点将作为起始顶点,因为其键值为0。当选择此顶点之后,将其标记为黑色。接下来,对于每个与u相邻的顶点v,设置v的键值为边(u,v)的权值,同时将u设置为v的父结点。重复这个过程,直到所有顶点都标记为黑色。随着最小生成树的增长,该树包含图中所有的边,且此边两端都有一个黑色的顶
- · 查看原书依据
最短路径估计。通常,最短路径估计由变量d表示。 开始,将所有色值设置为白色,最短路径估计设置为∞(它代表一个足够大的数,大于图中所有边的权值)。将起始顶点的最短路径估计设置为0。随着算法的不断演进,在最短路径树中为每个顶点(除了起始顶点外)指派一个父结点。在算法结束之前,顶点的父结点可能会发生几次变
参考来源
- 位置:《算法精解:C语言描述》第16章《Prim算法》(spine1409;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1375.html;u293-ch16-004)。
- 结论依据:293全文、03076全部六阶段图/父指针/权值实读;已读295源码比较表达式补足条件,割性质由MIT讲义相关Prim说明补核。
- 原始内容:键值最小的顶点u。开始,此顶点将作为起始顶点,因为其键值为0。当选择此顶点之后,将其标记为黑色。接下来,对于每个与u相邻的顶点v,设置v的键值为边(u,v)的权值,同时将u设置为v的父结点。重复这个过程,直到所有顶点都标记为黑色。随着最小生成树的增长,该树包含图中所有的边,且此边两端都有一个黑色的顶
- 位置:《算法精解:C语言描述》第16章《Dijkstra算法》(spine1412;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1378.html;u297-ch16-004)。
- 结论依据:297与293对照:Prim的key是从当前树连接到顶点的一条最小边权;Dijkstra的d是从源出发的累计路径估计。两者都选最小候选,但更新公式及非负边前提不能互换。
- 原始内容:最短路径估计。通常,最短路径估计由变量d表示。 开始,将所有色值设置为白色,最短路径估计设置为∞(它代表一个足够大的数,大于图中所有边的权值)。将起始顶点的最短路径估计设置为0。随着算法的不断演进,在最短路径树中为每个顶点(除了起始顶点外)指派一个父结点。在算法结束之前,顶点的父结点可能会发生几次变