最小生成树：Prim算法

大家好，欢迎来到IT知识分享网。

讲构建最小生成树的算法前，先来回顾一下什么是生成树，什么是最小生成树？生成树是指：在一个连通图Graph中，包含Graph中所有n个顶点的极小连通子图，一定包含Graph中的n-1条边（如果小于n-1条边，生成树会不连通。如果大于n-1条边，就一定会产生回路，那么就不是树了，树中不能产生回路）。且生成树不唯一。举个例子：

这个无向连通图的生成树分别有

什么是最小生成树？

1. 无回路，且包含原图中的n-1条边。
2. 包含原图中的全部顶点。
3. 边的权重和在所有其他生成树中最小。
4. 最小生成树存在，则该图一定连通。反过来一样，图连通，则最小生成树一定存在。

那么如何构建满足以上条件的生成树？这篇日志先介绍其中一种常用的普里姆（Prim）算法。Prim算法构建最小生成树，简单来说就是在图中，从某一顶点出发，逐步构建，让一棵小树逐渐长大。用一个例子来说明更清晰点吧！首先看下面一张无向网图：

要构造这张图的最小生成树，首先，假设我们从V0顶点开始出发，也就是以V0为根结点开始建树，接着往外扩展，从与V0顶点相邻的顶点中找出权值最小的顶点，可以看到是V6，所以把V6和V0连接起来。

也就是把V6收录进了这棵最小生成树中了。接着继续，从当前树中顶点的邻接点中（也就是V0和V6的邻接点中，找出权值最小的顶点）。可以看到是V1，所以把V1也接入最小生成树中。

然后继续，到V2结点，也接入最小生成树中

因为不能形成回路，所以V2和V6之间不能连接（虽然权值最小，等于3）。V0和V1之间也不能连接。所以只能V6和V4连接

最后V4和V5连接，V4再和V3连接，就完成了这棵最小生成树的构建了。

(最小生成树)

以上就是Prim算法构建最小生成树的过程。接下来看怎么用代码实现这个算法：

首先传进去我们的图MyGraph，和一个MST图，MST图用来存最小生成树。然后定义 两个一维数组dist和parent,

· parent数组存的是某个顶点的(下标表示)父结点parent[0]=-1表示V0为根结点。

· dist数组用来保存顶点Vj到VT顶点的边的最小权值(也就是某个结点到最小生成树MST的最小 距离),即存储各顶点与当前树的”距离”.如果Vj属于当前树,则dist[j]=0;。

然后是变量TotalWeight保存最小生成树的权重和。Vcount保存收录的顶点的个数，以及一条边E后面做构建生成树时插入顶点用。

这些变量都定义完后，就要开始对它们进行初始化。第142行开始初始化dist数组，默认初始点下标是0,也就是顶点V0到各个顶点的距离。初始化parent数组，暂时定义所有顶点的父结点都是初始点0,因为V0是根节点,一开始就它一个。权重和TotalWeight和收录的顶点个数Vcount都初始化为0。

然后初始化最小生成树MST图，就跟初始化一个新图一样，创建有Vertex个顶点但没有边的图（还是用邻接矩阵的方式）。第154行建立一个空的边结点，后面做树生长时插入顶点用。

初始化工作做完后，接着开始建树了（第157行开始），首先是初始点0（假设从V0顶点开始），把V0顶点收录进MST，因为结点V0是根结点,所以到最小生成树的距离更新为0（即dist[0]=0）。收录的顶点数Vcount++。parent[0]=-1是因为V0是根结点。

根结点处理好后，就要开始让小树生长了。我们可以用一个while循环，不断找出当前最小生成树的所有邻接点中“距离”最近的（也就是权值最小）的顶点，找到一个就把它插入进MST里，让最小生成树“生长”。那么循环什么时候结束？当然就是（第165行），当这个顶点找不到的时候就break退出while循环。

我们来看第163行开始，用一个FindMinDist函数找出未被收录的结点中距离当前树”距离”(即权值)最小的顶点赋给V。然后将V及相应的边 <parent[V], V>收录进MST（也就是说将顶点V和V的父结点插入到最小生成树中）。第176行，插入完这个新顶点后，更新TotalWeight权值和。以及结点V到最小生成树的距离更新为0（因为这个顶点已经融入到最小生成树当中了）。Vcount++表示收录到的顶点数加一。

   循环的最后一步就是扫描图上所有顶点，找出跟V相邻的顶点，V的邻接点，且是没被收录进最小生成树中的V的邻接点（dist[W]!=0即没被收录进最小生成树中，MyGraph->[V][W]<INFINITY即W是V邻接点）。第185行如果收录了V后能使得dist[W]变小，那么就更新一下dist[W]。

最后的最后，在执行完Prim算法的最后一步，就是判断下最小生成树MST中的顶点个数有没有达到原图中的顶点个数。如果没有达到，证明这个图不连通，就返回ERROR。构建成功就返回最小生成树的权重和TotalWeight。

还有一个函数FindMinDist函数要怎么做呢？

FindMinDist函数找出未被收录的顶点中dist最小值(即未被收录的顶点中距离当前最小生成树”距离”最短的顶点)。我们把原图MyGraph和dist数组传进去，定义两个变量MinIndex和V，MinIndex保存最小顶点的下标，初始化它为INFINITY。找未被收录的顶点中dist最小的顶点，就用一个循环扫描图中所有顶点，如果顶点没被收录，且顶点值小于MinDist的，就更新一下MinDist，并且把下标V更新给MinIndex。如果能够找到dist最小顶点的话，就把MinIndex返回出去，否则返回ERROR。

最后看下用邻接矩阵方式的Prim算法效果图：