以无向网表示n个城市之间通信网络建设计划，顶点表示城市，边上的权表示该线路造价
发布网友
发布时间：2022-04-23 11:55
共1个回答
热心网友
时间：2023-10-12 16:15
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 6 #define infinite 9999 long Prim(int path[N+1][N+1]); int main(int argc,char* argv[]) { int i,j; long result; int a[N+1][N+1]; memset(a,infinite,sizeof(a)); for(i=1;i<=N;i++) for(j=i+1;j<=N;j++) scanf("%d",&a[i][j]); for(i=1;i<=N;i++) for(j=1;j<=N;j++) a[j][i]=a[i][j]; printf("相邻城市之间距离：\n"); for(i=1;i<=N;i++) { for(j=1;j<=N;j++) printf("%d\t",a[i][j]); printf("\n"); } result=Prim(a); printf("the result is %d ",result); return 0; } long Prim(int path[N+1][N+1]) { int i,j,mini; long d[N],min,total; int visit[N]; total=0; for(i=1;i<=N;i++) { d[i]=path[0][i]; visit[i]=0; } d[1]=0; d[0]=0; for(i=0;i<N;i++) { min=infinite; for(j=1;j<=N;j++) if(d[j]<min&&!visit[j]) { min=d[j]; mini=j; } if(min==infinite) break; else { visit[mini]=1; for(j=1;j<=N;j++) if(!visit[j]&&path[mini][j]<d[j]) d[j]=path[mini][j]; } } printf("\n"); for(i=1;i<N+1;i++) { printf("%d->",d[i]); total+=d[j]; } return total; }
求采纳
