=0; for(i=0;i<g.vexnum;i++) { if(m==0 && a[i].lowcost!=0) { m=1; k=i; } if(m==1 && a[i].lowcost!=0) { if(a[i].lowcost<a[k].lowcost) k=i; }} return k;}8 ④普利姆算法求最小生成树,输出最优线路及费用 void MiniSpanTree_PRIM(Graph g,char a[10]) { struct tree closedge[M]; int i,j,k,money=0; k=locatevex(&g,a); for(i=0;i<g.vexnum;i++) { if(i!=k) { closedge[i].lowcost=g.R[k][i]; closedge[i].weizhi=k; }} closedge[k].lowcost=0; for(i=1;i<g.vexnum;i++) { k=minimun(closedge,g); money+=closedge[k].lowcost; printf("%d:%s %s %d\n",i,g.V[closedge[k].weizhi],g.V[k],closedge[k].lowcost); closedge[k].lowcost=0; for(j=0;j<g.vexnum;j++) { if(g.R[k][j]<closedge[j].lowcost) { closedge[j].weizhi=k; closedge[j].lowcost=g.R[k][j]; } 9 }} printf(" 总费用为: % d\n",money); } 4.3.2 函数的调用关系图 locatevex minimun creatgraph main MiniSpanTree_PRIM 结束
全文预览
