通信网规划实验报告

《通信网规划实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、学生实验报告课程名称通信网规划实验专业通信工程姓名&謹&&学号班级教师实验一：Kruskal算法求最小生成树一、实验原理：设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树屮去。如果在放置某-条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有n-1条边时，我们所得到的就是一颗最小生成树。二、实验步骤：(1)边依小到大顺序得h，12，…，L。(2)置初值：0=>S,O^i,l^jo(3)若i=n-l,则转(6)o(4)若生成树边集S并入一条新的边b

2、之后产生的冋路，则并转(4)。(5)否则，i+1二i;I^S(i)；j+lsj，转(3)。(6)输出最小生成树S。(7)结朿。三、实验程序：Kruskal算法求FI的最小生成树#include#include#dcfincMaxVcrtcxNum12#dcfincMaxEdgcNum20#dcfincMaxValue1000typedefintVertexType;typedefVertexTypevcxlist[MaxVcrtcxNum];typedefintadjmatrix[MaxVcr

3、tcxNum][MaxVcrtcxNum];intvisitcd[MaxVcrtcxNum]={0};structcdgcElcmintfromvex;/*边的起点域*/intendvex;/*边的终点域*/intweight;/*边的权值域*/typedefstructedgeElemedgeset[MaxEdgeNum];voidKi-uskal(edgesetGE，edgesetC，intn){intI，j，k，d,ml，m2;adjmatrixs;for(i=0;i

4、j)s[i]U]=l;elses[i][j]=O;}k=l;d=0;while(k

5、

6、s[m2]D]；s[m2][j]=0;d++;voidCreate(vexlistGV，edgesetGE，intn，inte)/*建立顶点数组GV和边集数组GE*/in

7、tI，j,k，w;printfC‘输入％(1个顶点数据”，n);for(i=0;i

8、“，GE[i].fromvex，GE[i].endvex,GE[i].weight);printf(“”)；main()intn，e;vexlistgv;adjmatrixga;edgesetge，c;printf(“输入图的顶点数和边数:”)；scanf(‘‘％d%d’’，&n，&e);Create(gv，ge，n，e);printf(“利川Kruskal算法从顶点0出发求图的最小生成树:”);Kruskal(ge,c,n);outputEdgeset(c，n-1);getch();实验结果:（一）输入如图的顶点数、边数

9、及各边权值:顶点数、边数：79FG2各边权值：AB2，BG6,AC2，BC4,CF1，AD4,DE5,EF3,应用C++运算实现Kruskal算法求最小生成树:通过实验可得：本实验所给图的最小生成树为：A-C2,C-F1，F-G2,A-B3,F-E3,A-D4即最小度和=2+1+2+3+3+4=15实验二：Excel线性规划求解求网络最短路实验内容：一网络节点如图所示，利用Excel线性规划求解工具求解从起点s到终点t的最小价格设计方案。网络节点间的数字表示网络铺设距离。假设个节点间单位网络铺设成本相等。实验原理：需要计算从VI点

10、到V8点的最短路径。用excel求解最短路径的原理是：令变量为0或者1.即如果最短路径通过vlv2,v2v4......,z则变量设为1，不通过则为0，除起点或者终点之外，舟个点的进出权数和是0，起点的进出权数和是1，终点是-1，目标函数是各边权数