Prim算法的实现定义

为了防止我说不清，先贴一下官方解释，引自《大话数据结构》：

假设N = (P, {E})是连通图，TE是N上最小生成树中边的集合。算法从U = {u0}(u0∈V)，TE = {}开始。重复执行下述操作：在所有u∈U, v∈V - U的边(u, v)∈E中找一条代价最小的边(u0, v0)并入集合TE，同时v0并入U，直到U = V为止。此时TE中必有n - 1条边，则T = (V, {TE})为N 的最小生成树。

记录一下我的理解

简单来讲

• 1、我们可以随意假定一个起始点v0，遍历图中所有的顶点并记录与v0的距离(无边/弧的记为无穷大即可)，在这些距离中找到最小的一条边/弧，该边的另一个顶点记为vk，将该顶点加入最小生成树的顶点集中；
• 2、现在以vk点为边的起点，遍历整个图的(除已在最小生成树顶点集的点外)顶点，并与之前存储的距离比较，取小的距离值更新，最后再次找其中最小的距离值，记录另一个顶点vk‘，并加入到最小生成树的顶点集中；
• 3、重复，直到最小生成树的顶点集涵盖所有顶点。

在程序中，我们可以用adjvex[i]表示第i个顶点在当前距离最小的边的另一个顶点(这个顶点已在最小生成树顶点集U中)的索引；lowcost[i]数组表示第i个顶点在当前距离最小的边，所以可以理解为边(i, adjvex[i])的权值就是lowcost[i]，而这个权值是当前已加入到最小生成树顶点集U中的所有顶点与第i个顶点的最小权重；然后再在lowcost[]数组中找到最小的一个权值，将其顶点i加入U中，再更新(只有权值更小才能更新)整个lowcost数组和对应adjvex[]值。

C++代码实现