通信网络设计new

1、如果以无向网表示N个城市之间通信网络的建设计划，顶点表示城市，边上的权表示该线路的造价，设计一个方案，使这个通信网的总造价最低。实现提示：这是一个求连通的带权无向图的最小代价生成树的问题。建立图的邻接矩阵，然后以prime算法来求最小生成树。算法实现：设图的顶点集合V有N个顶点，prime算法粗略描述如下：（1） 设置一个顶点的集合S1和一个边的集合TE，S1和TE的初始状态皆为空集。（2） 选定图中的一个顶点k(从此顶点开始求最小代价生成树)，将k加入集合S1。（3） 重复下列步骤，直至选取了n-1条边： 选取一条权值最小的边(x,y)，其中xS1，y S1。 将顶点y加入集合 S1，边(x

2、,y)加入集合TE。参考程序：# include <stdio.h># define n 5# define max 1000.0typedef struct node int no; float wgt; struct node *next; edgenode;typedef struct char vtx; edgenode *link; vexnode;float gali nn = 0,2,12,10,max,2,0,8,max,9,12,8,0,6,3,10,max,6,0,7,max,9,3,7,0;typedef vexnode Graphn;Graph G;void

3、 prim(vexnode G,int k) int v2linkn, vsetn,parentn,wn; edgenode *ptr ; int x, s, ecount, i, y, z, f; s=-1; x = k; vsetk = -1; v2linkn = -1; ecount=0; for(i=0;i<n;i+) if(i!=k) vseti=3; while(ecount<n-1) ptr=Gx.link; while(ptr!=Null) y=ptr->no; if(vsety= =2)&&(ptr->wgt<wy) /*y在集合

4、v2*/ parenty = x; wy=ptr->wgt; if(vsety= =3) /*y在集合v3*/ vsety=2; v2linky=s; s=y; parenty = x; wy=ptr->wgt;ptr = ptr->next; if(s= =-1) break; /*无最小代价生成树*/ z=x=s; y=v2linkx; f=-1; while(y!=-1) if(wy<wx) x=y;f=z; z=y; y=v2linky;if(f= =-1) s=v2linkx;else v2linkf=v2linkx;vsetx=1;ecount+; /*边数

5、计数*/printf(“nroot%c:t”, Gk.vtx); /*输出结点*/for(i=0;i<n;i+)if(i!=k) printf(“%c”,Gi.vtx); f=parenti; printf(“%ct”, Gf.vtx);void creatlist(vexnode ga) int i, j, k, e, w; edgenode *se; for(i=0; i<n; i+) gai.vtx=a+i; for(j=0;j<n;j+) if(galiij<max)&&(galiij!=0) se=(edgenode*)malloc(sizeof(*se); se->no=j; se->next=gai.link; se->wgt=galiij; gai.link=se;main() int i; edgenode *ve; creatlist(G); for(i=0;i<n;i+) printf(“n v%c=link:”,Gi.vtx); ve=Gi.link; while(v