通信网络设计new

《通信网络设计new》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、合S1，边(x,y)加入集合TE。参考程序：#include#definen5#definemax1000.0typedefstructnode{intno;floatwgt;structnode*next;}edgenode;typedefstruct{charvtx;edgenode*link;}vexnode;floatgali[n][n]={{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}};typedefvexnodeGraph[n];GraphG;vo

3、idprim(vexnodeG[],intk){intv2link[n],vset[n],parent[n],w[n];edgenode*ptr;intx,s,ecount,i,y,z,f;s=-1;x=k;vset[k]=-1;v2link[n]=-1;ecount=0;for(i=0;ino;if((vset[y]==2)&&(ptr->wgt

4、=ptr->wgt;}if(vset[y]==3)/*y在集合v3*/{vset[y]=2;v2link[y]=s;s=y;parent[y]=x;w[y]=ptr->wgt;}ptr=ptr->next;}if(s==-1)break;/*无最小代价生成树*/z=x=s;y=v2link[x];f=-1;while(y!=-1){if(w[y]

5、root%c:t”,G[k].vtx);/*输出结点*/for(i=0;i

6、);se->no=j;se->next=ga[i].link;se->wgt=gali[i][j];ga[i].link=se;}}}}main(){inti;edgenode*ve;creatlist(G);for(i=0;ino,ve->wgt);ve=ve->next;}}prim(G,4);return0;}