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 }
讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/137752.html