数据结构——图——普里姆（Prim )算法

旧城等待， 2023-01-11 14:27 129阅读 0赞

## 数据结构——图——普里姆（Prim )算法 ##

我们先构造图7-6-1的邻接矩阵，如图7-6-3的右图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]  
也就是说，现在我们已经有了一个存储结构为MGragh 的G。G有9个顶点，它的arc二维数组如图7-6-3的右图所示。数组中的我们用65535来代表oo。

于是普里姆(Prim）算法代码如下，左侧数字为行号。其中INFINITY为权值极大值，不妨是65535，MAXVEX为顶点个数最大值，此处大于等于9即可。现在假设我们自己就是计算机，在调用MiniSpanTree\_Prim函数，输入上述的邻接矩阵后，看看它是如何运行并打印出最小生成树的。

/*邻接矩阵的结构*/
    typedef char VertexType;  /*顶点类型应由用户定义*/
    
    typedef int EdgeType; /*边上的权值类型应由用户定义*/
    
    #define MAXVEX 100   /*最大顶点数，应由用户定义*/
    
    #define INFINITY 65535  /*用65535来代表*/
    
    typedef struct
    {
        
    	VertexType vexs[MAXVEX];   /*顶点表*/
    	EdgeType arc[MAXVEX][MAXVEX];  /*领边矩阵，可看作边表*/
    
    	int numVertexes, numEdges;    /*图中当前的顶点数和边数*/
    } MGraph;
    
    /*普里姆（Prim）算法*/
    
    void MiniSpanTree_Prim(MGraph G)
    {
        
    	int min, i, j, k;
    	int adjvex[MAXVEX];   /*保存相关顶点下标*/
    	int lowcost[MAXVEX];  /*保存相关顶点间边的权值*/
    	lowcost[0] = 0;      /*初始化第一个权值为0，即v0 加入生成树*/
    	                /*lowcost的值为0，在这里就是此下标的顶点已经加入生成树*/
    	adjvex[0] = 0;  /*初始化第一个顶点下标为0*/
    	for (i=1;i<G.numVertexes;i++)/*循环除下标为0外的全部顶点*/
    	{
        
    		lowcost[i] = G.arc[0][i];/*将顶点与之有边的权值存入数组*/
    		adjvex[i] = 0;           /*初始化都为v0的下标*/
    	}
    
    	for (i = 1; i < G.numVertexes; i++)
    	{
        
    		min = INFINITY;/*初始化最小值为oo*/
    		                /*通常设置为不可能的大数字如32767,65535等*/
    
    		j = 1; k = 0;
    		while (j<G.numVertexes)    /*循环全部顶点*/
    		{
        
    			if (lowcost[j]!=0&& lowcost[j]<min)
    			{
        
    				/*如果权值不为0 且权值小于min*/
    				min = lowcost[j];  /*则让当前权值成为最小值*/
    				k = j;             /*将当前最小值的下标存入k*/
    			}
    			j++;
    		}
    
    		printf("(%d,%d)", adjvex[k], k);/*打印当前顶点边中权值最小边*/
    		lowcost[k] = 0;/*将当前顶点的权值设置为0，表示此顶点已经完成任务*/
             for (j=1;j<G.numVertexes;j++) /*循环所有顶点*/
             {
        
    			 if (lowcost[j]!=0&&G.arc[k][j]<lowcost[j])
    			 {
        
    				 lowcost[j] = G.arc[k][j];/*将较小权值存入lowcost*/
    				 adjvex[j] = k;/*将下标为k的顶点存入adjvex*/
    			 }
             }
    	}
    }

1．程序开始运行，我们由第4~5行，创建了两个一维数组lowcost和 adjvex,长度都为顶点个数9。它们的作用我们慢慢细说。

2．第6～7行我们分别给这两个数组的第一个下标位赋值为0，arjvex\[0\]=0其实意思就是我们现在从顶点vo开始（事实上，最小生成树从哪个顶点开始计算都无所谓，我们假定从v0开始)，lbwcost\[0\]=0就表示vo已经被纳入到最小生成树中，之后凡是 lowcost 数组中的值被设置为0就是表示此下标的顶点被纳入最小生成树。

3．第8~12行表示我们读取图7-6-3的右图邻接矩阵的第一行数据。将数值赋值给lbwcost数组，所以此时lowcost数组值为\{0,10,65535,65535,65535,11,65535,65535,65535\}，而 arjvex 则全部为0。此时，我们已经完成了整个初始化的工作，准备开始生成。

4．第13～36行,整个循环过程就是构造最小生成树的过程。

5．第15～16行，将min设置为了一个极大值65535，它的目的是为了之后找到一定范围内的最小权值。j是用来做顶点下标循环的变量，k 是用来存储最小权值的顶点下标。

6.第17~25行，循环中不断修改min为当前lbwcost 数组中最小值，并用k保留此最小值的顶点下标。经过循环后，min=10，k=1。注意19行if 判断的lowcost\[j\]!=0表示已经是生成树的顶点不参与最小权值的查找。

7．第26行，因k=1，adjvex\[1\]=0，所以打印结果为（0，1)，表示vo至v边为最小生成树的第一条边。如图7-6-4所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]  
8．第27行，此时因k=1我们将bwcost\[k\]=0就是说顶点v纳入到最小生成树中。此时lbowcost数组值为\{0,0,65535,65535,65535,11,65535,65535,65535\}。

9．第28~35行,j循环由1至8，因k=1，查找邻接矩阵的第v1行的各个权值，与bwcost的对应值比较，若更小则修改lbwcost值，并将k值存入adjvex 数组中。因第v行有18、16、12均比 65535小，所以最终 lbwcost数组的值为:\{0,0,18,65535,65535,11,16,65535,12\}。adjvex数组的值为:\{0,0,1,0,0,0,1,0,1\}。这里第30行if 判断的lbwcost\[j\]!=0也说明vo和vi已经是生成树的顶点不参与最小权值的比对了。

10．再次循环，由第15行到第26行，此时min=11，k=5，adjvex\[5\]=0。因此打印结构为(0，5)。表示 vo至vs边为最小生成树的第二条边，如图7-6-5所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 2]  
11．接下来执行到36行，lbwcost数组的值为:\{0,0,18,65535,26,0,16,65535,12\}。adjvex数组的值为:\{0,0,1,0,5,0,1,0,1\}。

12．之后，相信大家也都会自己去模拟了。通过不断的转换，构造的过程如图7-6-6中图1～图6所示。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 3]  
有了这样的讲解，再来介绍普里姆（Prim）算法的实现定义可能就容易理解一些。

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

普里姆算法对于稠密图,即边数非常多的情况会更好一些

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]: /images/20221119/cf9b40411ea24b129fc8df567131fd74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2021012709164667.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210127091832899.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2021012709194839.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ==,size_16,color_FFFFFF,t_70