资源描述:
《通信网络设计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->wgt4、=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;i6、);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;}