Prim算法

基本思想

1. 取图中任意一个顶点作为生成树的根，之后往生成树上添加新的顶点 w。
2. 在添加的顶点 w 和已经在生成树上的顶点之间必定存在一条边，并且该边的权值在所有连通顶点 w 和已在树上的顶点之间的边中取值最小。
3. 继续往生成树上添加顶点，直至生成树上含有 n 个顶点为止。

数据结构

具体来说，维护额外两个数组：

• AdjVex 数组：用来存储从哪一个顶点到该节点代价最小。
• LowCost 数组：用来存储到达该顶点的最小代价。

执行步骤

1. 初始化：从某个起始顶点开始，将其加入生成树，初始化 AdjVex 和 LowCost 数组。
2. 每次寻找 LowCost 值最小的顶点（代价最小的顶点），将其加入生成树。
3. 遍历该顶点的相邻顶点，更新相邻顶点的表值：
   • 如果从当前顶点到相邻顶点的代价比当前 LowCost 中的代价小，则将 LowCost 更新为新代价。
   • 将 AdjVex 中的对应顶点改为当前顶点。
4. 重复步骤 2-3，直到所有的顶点都被遍历（生成树包含所有顶点）。

链接到

• 上一个知识点：7.6 生成树和最小生成树
• 下一个知识点：7.8 Kruskal算法