普利姆算法

浅浅的花香味﹌ 2022-08-07 12:50 166阅读 0赞

普利姆(Prim),这个算法有什么用?在实际中这个算法经常用到电子板的电路连线中,因为可以使用到最少的连线将所有的电子连接起来,又打个比方在铺设电线将所有用户连接起来可以使用最少的电线连接起来!知道了这个作用之后你是不是比较感兴趣呢?

首先看代码:

//Prim算法生成最小生成树
 void MiniSpanTree_Prim(MGraph G){
 	int min,i,j,k;
 	int adjvex[MAXVEX];//保存相关顶点的下表
 	int lowcost[MAXVEX];//保存相关顶点间的权值
 	lowcost[0]=0;//V0 作为最小生成树的根开始遍历,权值为0
 	adjvex[0]=0;//V0 第一个加入
 	//初始化操作,根据图示例G.numVertexes=8	步骤一,请看图2
 	for(i=0;i<G.numVertexes;i++){
 		lowcost[i]=G.arc[0][i];
 		adjvex[i]=G.arc[0][i];
 	}
 	//构造最小生成树的过程,根据图示例G.numVertexes=8
 	for(i=0;i<G.numVertexes;i++){
 		min=INFINITY;//初始化最小权值为65535等不可能数值
 		j=1;k=0;
 		//遍历全部顶点	步骤二,请看图3
 		while(j<G.numVertexes){
 			//找出lowcost数组已存储的最小权值
 			if(lowcost[j]!=0 && lowcost[j]<min){
 				min=lowcost[j];
 				k=j;//得到最小k的索引
 			}
 			j++;
 		}
 		//打印出当前顶点中权值最小的边
 		printf("(%d,%d)",adjvex[k],k);
 		lowcost[k]=0;//将当前顶点的权值重置为0,表示该顶点已经完成遍历了
 		//邻接矩阵k行逐个遍历全部顶点	步骤三:请看图4
 		for(j=0;j<G.numVertexes;j++){
 			if(lowcost[j]!=0 && G.arc[k][j] <lowcost[j]){
 				//保存关联的最小的权值
 				lowcost[j]=G.arc[k][j];
 				adjvex[j]=k;//重新定位一下对应的索引
 			}
 		}
 	}
 }

看完了代码是不是有点晕?我们进行代码算法模拟,结合图文说明:

图1:先理解一下各个参数的说明:

![20150410174013507][]

图2:

![20150413100226879][]

图3,并且打印出了 权值10,顶点1,打印出了之后将lowcost\[1\]的权值=0:

![20150413095019418][]

图4,从图4可以推出下一次我们打印出的是,权值11,顶点5:

![20150413095555315][]

[20150410174013507]: /images/20220805/c77dd6c6317249119ef5550670066463.png
[20150413100226879]: /images/20220805/d68aad21026d446ebbd6f9c044085f2e.png
[20150413095019418]: /images/20220805/d8af6edda52c453d9531f1d24a024b97.png
[20150413095555315]: /images/20220805/01eb668bf58d44b692a63b975c487e1a.png