6.4.1.1 Prim 算法

教材导航 · 第6章

原书定位

印刷页P232起,对应PDF第244页。下文为目视整理的知识提要;完整内容见原书对照。

从一个顶点开始,维护一棵逐渐扩展的树。每次选择连接树内顶点与树外顶点的最轻边,把对应顶点加入树,再更新其他顶点到当前树的最小连接权。

朴素矩阵实现 O(n2)O(n^2),适合稠密图。这里维护的是到当前树的一条最轻连接边,与 Dijkstra 的“到源点的整条路径长度”不同。若余下最小连接权为无穷,说明图不连通,无法继续构造覆盖全图的树。

Prim 构造过程

Prim 构造过程,原书P232。

对应练习

6.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P232,PDF第244页

原书对照,原书P233,PDF第245页