最小生成树之Prim（普里姆）算法

注明：本博客参考《数据结构教程》第4版

（一）知识准备

在开始学习Prim算法之前，我们需要对图有一定的了解，且知道图的存储方式（本博客基于无向图和邻接矩阵的知识），同时我们要了解什么是生成树？一个连通图的生成树是该连通图的一个极小连通子图，它是含有图的全部顶点，但只有构成一棵树的（n-1）条边，而最小生成树则是在生成树的基础上，要求树的（n-1）条边的权值之和是最小的。由此可以总结构造最小生成树的要求有：（1）必须只使用该图中的边来构造最小生成树；（2）必须使用且仅使用（n-1）条边来连接图中的n个顶点；（3）不能使用产生回路的边；（4）要求树的（n-1）条边的权值之和是最小的。

（二）算法初识

接着开始我们的Prim算法的学习！首先我们先来认识下Prim算法的基础认识（后面我们会更加严谨的给出其定义与推算过程）：通过选点来构造最小生成树，每次（第一次
可随意挑选）从中挑选当前最适合的（即选俩点的权值最小的，使构造的当前生成树最小）点来构造最小生成树。

（三）算法实例演示

首先让我们来看一个example。如下图所示，图a是一个连通图（右图是图a对应的邻接矩阵，假设图中的边的权值大于0），我们现在基于该图来演示Prim算法的过程。

我们选择一个起点，然后在与起点相连且未被选的节点中选择一个权值最小的节点，将该节点与其相连边添加入生成树。假设起点是0节点，与0节点相连且未被选的节点是{1,2,3}，分别对应的权值是{
6,1,5}，可见当前最小的权值1，权值最小的节点就是2节点，所以将2节点和0-2的边添加入生成树，如图b所示。

接着我们在与已选节点相连且未被选的节点中选择一个权值最小的节点，将该节点与其相连边添加入生成树。当前已选节点是0,2节点，与已选节点相连且未被选的节点有{1,3,4,5}，分别对应的权值是{（6,5），（5,5），6,4,}，可见当前最小的权值4，权值最小的节点就是5节点，所以将5节点和2-5的边添加入生成树，如图c所示。（其实在编程时，我们只需记录与更新当前较小的那个权值，如与{1,3,4,5}对应的权值我们只需记录{5,5,6,4}，当然我们也需利用了另一个数组来加以区别当前权值对应的连接点，如当前权值{5,5,6,4}所对应的连接点就是{2,0,2,2}）

接着我们继续在与已选节点相连且未被选的节点中选择一个权值最小的节点，将该节点与其相连边添加入生成树。当前已选节点是0,2,5节点，与已选节点相连且未被选的节点有{1,3,4}，分别对应的权值是{（6,5），（2,5,5），（6,6）,}（其实当前我们可只记录{5,2,6}，同时记录其对应的连接点分别是{2,5,2}），可见当前最小的权值2，权值最小的节点就是3节点，所以将3节点和5-3的边添加入生成树，如图d所示。

接着我们依照上一次的步骤继续在与已选节点相连且未被选的节点中选择一个权值最小的节点，将该节点与其相连边添加入生成树。如图e，f所示。最终图f就是我们通过Prim算法得到的最小生成树了。

（四）算法概念

现在我们给出Prim的严谨概念：Prim算法是一种构造性算法。假设G=（V,E）是一个具有n个顶点的带权连通无向图，T=（U，TE）是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始顶点v出发的最小生成树T的步骤如下：

（1）初始化U={v},以v到其他顶点的所有边为候选边；

（2）重复以下步骤（n-1）次，使得其他（n-1）个顶点被加入到U中：

1.从侯选边中挑选权值最小的边加入TE，设该边在V-U中的顶点是k，将k加入U中；

2.考察当前V-U中所有顶点j，修改侯选边，若边（k，j）的权值小于原来和顶点j关联的侯选边，则用边（k，j）取代后者作为侯选边

现在我们可以来编程实现Prim算法啦！

（五）编程实现

首先，在动手编程之前我们需要了解我们考虑实现Prim算法的一些相关的东西。

第一个考虑的便是传入的参数，第一个参数就是无向图的信息（这里我们用邻接矩阵MGraph来存储），第二个参数是起点。下面给出邻接矩阵的结构体。

//邻接矩阵的数据类型 #define MAXV 50 //最大顶点数 typedef struct { int no;//顶点编号 //InfoType info;//顶点的其他信息 }VertexType;//顶点类型 typedef struct { int edges[MAXV][MAXV];//邻接矩阵的边数组 int n, e;//顶点数，边数 VertexType vexs[MAXV];//存放顶点信息 }MGraph;//图邻接矩阵类型 #define INF 32767//表示无穷大

下面来介绍实现Prim算法的一些重要的变量或结构。

为了便于选中当前权值最小的边的节点，需要建立两个数组closest和lowcost，对于某个未选中的节点j，lowcost[j]存储的是节点j与当前已选节点相连的最小权值（lowcost[j]==0表示节点j已被选），closest[j]存储lowcost[j]对应的连接点，如下图所示。

按照上面例子（即按图a得到最小生成树），其求解过程中lowcost数组和closest数组的变化，如下图所示（希望读者结合下面的程序代码来分析这两个数组）。

现在我们可以动手编程了！代码如下：

void Prim(MGraph g, int v)//普利姆算法（参数：邻接矩阵，起点（即第一个生成的点，可随便取）） { int lowcost[MAXV], closest[MAXV], i, min, j, k; /*初始化lowcost数组，closest数组(即从起点开始设置lowcost数组，closest数组相应的值，以便后续生成使用)*/ for (i = 0; i < g.n; i++)//赋初值，即将closest数组都赋为第一个节点v，lowcost数组赋为第一个节点v到各节点的权重 { closest[i] = v; lowcost[i] = g.edges[v][i];//g.edges[v][i]的值指的是节点v到i节点的权重 } /开始生成其他的节点*/ for (i = 1; i < g.n; i++)//接下来找剩下的n-1个节点（g.n是图的节点个数） { /*找到一个节点，该节点到已选节点中的某一个节点的权值是当前最小的*/ min = INF;//INF表示正无穷（每查找一个节点，min都会重新更新为INF，以便获取当前最小权重的节点） for (j = 0; j < g.n; j++)//遍历所有节点 { if (lowcost[j] != 0 && lowcost[j] < min)//若该节点还未被选且权值小于之前遍历所得到的最小值 { min = lowcost[j];//更新min的值 k = j;//记录当前最小权重的节点的编号 } } /输出被连接节点与连接节点，以及它们的权值*/ printf("边(%d,%d)权为:%d\n", closest[k], k, min); /*更新lowcost数组，closest数组，以便生成下一个节点/ lowcost[k] = 0;//表明k节点已被选了(作标记) //选中一个节点完成连接之后，作数组相应的调整 for (j = 0; j < g.n; j++)//遍历所有节点 { /* if语句条件的说明： * （1）g.edges[k][j] != 0是指k！=j，即跳过自身的节点 * （2）g.edges[k][j]是指刚被选的节点k到节点j的权重，lowcost[j]是指之前遍历的所有节点与j节点的最小权重。若g.edges[k][j] < lowcost[j],则说明当前刚被选的节点k与节点j之间存在更小的权重，则需要更新 * （3）有人会问：为什么只跳过掉自身的节点（即k==j），而不跳过所有的已选节点？当然我们可以在if语句条件中增加跳过所有的已选节点的条件（即lowcost[j] == 0），而在本程序中我们只跳过了自身的节点？（注意：我们假设图中的边的权值大于0）但其实不是，g.edges[k][j] < lowcost[j]条件已包含跳过所有的已选节点，原因是在邻接矩阵中权值为0是最小的，即g.edges[k][j]>=0，而已选节点满足lowcost[j] == 0，则已选节点j是不满足g.edges[k][j] < lowcost[j]，则会被跳过 */ if (g.edges[k][j] != 0 && g.edges[k][j] < lowcost[j]) { //更新lowcost数组，closest数组 lowcost[j] = g.edges[k][j];//更新权重，使其当前最小 closest[j] = k;//进入到该if语句里，说明刚选的节点k与当前节点j有更小的权重，则closest[j]的被连接节点需作修改为k } } } }

Prim算法中有两重for循环，所以时间复杂度为O(n^2)，其中n为图的顶点个数。

本人是一个喜欢算法的新手，本博客以自己的理解简要的介绍了Prim算法，若本博客有错误需要修改的或对排版风格有要改进的等建议，请留言或发邮件给我。写博客是一个相互学习的过程，期待收到您的建议！记住，不要沮丧，好好学习，天天向上！共勉！