prim算法代码详解（prim算法adjvex）



 1 void MiniSpanTree_Prim(MGragh G)  2 {  3 int mini,i,j,k;  4 int adjvex[MAXVEX]; //保存相关顶点下标  5 int lowcost[MAXVEX]; //保存相关顶点间边的权值  6 lowcost[0] = 0;//这里把第0位的权值置0表示v0已加入生成树  7 //ps：lowcost[i] = 0 表示i那个下标的顶点加入生成树  8 adjvex[0] = 0; //初始化第一个顶点的下标为0  9 for(i = 0; i < G.numVertexes; i++) 10  { 11 lowcost[i] = G.arc[0][i];//将vo相关顶点的权值存入lowcost数组 12 adjvex[i] = 0;//置所有下标为v0 13  } 14 for(i = 1; i < G.numVertexes; i++) //最小生成树开始辽 15  { 16 mini = INFITINY; //先把权值的最小值置为无限大 17 j = 1; 18 k = 0; 19 while(j < G.numVertexes) 20  { 21 if(lowcost[j] != 0 && lowcost[j] < mini)//判断并向lowcost中添加权值 22  { 23 mini = lowcost[j]; 24 k = j; 25  } 26 j++; 27  } 28 printf("(%d %d)",lowcost[k],k); 29 lowcost[k] = 0;//置0表示这个定点已经完成任务，找到最小权值分支 30 for(j = 1; j < G.numVertexes; j++) 31  { 32 if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) 33  { 34 lowcost[j] = G.arc[k][j]; 35 adjvex[j] = k; 36  } 37  } 38  } 39 }

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rfx/27117.html