6.4.1.1 Prim 算法
原书定位
印刷页P232起,对应PDF第244页。下文为目视整理的知识提要;完整内容见原书对照。
从一个顶点开始,维护一棵逐渐扩展的树。每次选择连接树内顶点与树外顶点的最轻边,把对应顶点加入树,再更新其他顶点到当前树的最小连接权。
朴素矩阵实现 ,适合稠密图。这里维护的是到当前树的一条最轻连接边,与 Dijkstra 的“到源点的整条路径长度”不同。若余下最小连接权为无穷,说明图不连通,无法继续构造覆盖全图的树。

Prim 构造过程,原书P232。
对应练习
关联知识
原书对照
展开原书对照截图

