最小生成树

假设你是电信的实施工程师，需要为一个镇的九个村庄架设通信网络做设计，村庄位置大致如图，其中V0~V8是村庄，之间连线代表可达距离，数字代表里程数。领导要求你用最小成本完成这次任务，如何做？

显然这是一个带权值的图，即是网结构。所谓最小成本，就是n个顶点，用n-1条边把一个连通图连接起来，并使得权值和最小。

定义

一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一个树的n-1条边——我们把构造连通网的最小代价生成树称为最小生成树（Minimum Cost Spanning Tree）

我想在讲算法之前我们先做一下思考，我们如何找到该条路径？

• 我们是否可以从某一点开始寻找呢？
• 我们从哪一个地点作为起始点呢？
• 我们找到第一个点以后如何找最小权值的边呢？

第一步
我想先从概念下手：
首先，因为一个连通图含有图中全部顶点，所以我们可以从任意顶点出发（开始寻找），最终结果应该是一致的。但是为了方便讲述我还是想从V0开始出发（此时我们站在V0）。

起始点找到了，那么如何找起始点到第一个顶点的边呢？

逆着想一下，与V0邻接有且仅有两条边（V0,V1）,（V0,V5），我们必须要选一条（因为我们必须要到达V0），所以我们干脆在V0的两条边上选一条到达V0。

我们站在V0巡视了一下两条边，然后选择了（V0,V1）（此处有判断）。

然后我们记录一下V0我们已经走过，走过的路标记为红色。

第二步
但是接下来我们该如何走呢？
其实我也很迷茫，既然不知道，那就选当前能走的路的最近的一条吧。
现在我们有两种选择，第一种从V0出发，第二种从V1出发，分别产生的可能性如下（绿色）：

选一条最短的

接下来看V5和V1能到达哪里？然后继续寻找…直到最后一个顶点被连通（从0-n的循环）
其实这就是普里姆算法的核心思路，既然思路知道了，我们对比算法来讲解吧。

普里姆（Prim）算法

在讲之前我们先选一种图的存储结构吧，这里我们用图的邻接矩阵存储结构来讲解。

• 39-47行就是上面讲述的寻找我们当前顶点邻接的最小权值边，(用之前的例子讲：第一次循环是顶点V0所有的边，第二次循环除去边(V0,V1)以后顶点V0和V1所有的边，以此类推）
• 而51-58行则是更新当前所有可能的边的最小权值。
• 算法比较晦涩的是adjvex[MAXVEX]和lowcost[MAXVEX]的理解，一旦理解这两个数组的含义，这个算法也就没难点了。

由代码中的循环嵌套可得知此算法的时间复杂度为O(N^2)。