数据结构课程设计-最小通信网.docVIP

课 程 设 计 报 告 课程名称 数据结构课程设计 题 目 最小通信网 指导教师 设计起始日期 5.2~5.9 学 院 计算机学院 系 别 计算机科学与工程 学生姓名 班级/学号 成 绩 需求分析 要在n个城市之间建立通信网，已知各个城市间的距离，建立的通信线路要使得这n个城市相连，而且建立的通信网络代价最小。 输入：n个城市的距离关系图，即图的顶点和边上的权值 输出：含n个城市顶点的最小生成树中的边和代价 功能：建立图的最小生成树 测试数据：自选 概要设计 数据结构 用图来描述n个城市之间的关系，顶点为城市，边位两个城市间的代价 使用算法： 采用prim算法 算法思想：假设G=(V,E)为待求图，其中V为图中所有顶点的集合，E为带权图中所有带权边的集合。设置两个新的集合U和TE，其中集合U用于存放G的最小生成树中的顶点，集合TE存放G的最先生成树的边。令集合U的初值U={u1}（假设构造最小生成树时，顶点从u0出发），集合TE的初值为TE={}。Prim算法的思想是，从所有u∈U，v∈V-U的边中，选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u，v）加入集合TE中，如此不断重复，直到U=V，最小生成树树构造完毕，这时集合TE中包含了最小生成树的所有边 Prim算法可用下述过程描述，其中用wuv表示顶点u与顶点v边上的权值。（1）U＝{u1},T={}; （2）while (U≠V)do  (u，v)＝min{wuv；uU，vV－U } T＝T＋{(u，v)}  U＝U＋{v} typedef struct{ int Vnum;/*图的顶点数*/ int Arcs[MAXN][MAXN];/*邻接矩阵*/ }Graph;/*图的邻接矩阵存储法*/ 2、最小生成树PRIM算法: 在Prim算法中，应当考虑如何有效地找出满足条件i(U,j(V-U，且权c[i][j]最小的边(i,j)。实现这个目的的较简单的办法是设置2个一维数组closest和lowcost。Lowcost[j]中存储i(U,j(V-U且权最小的边(i,j)的权值c[i][j]，而closest[j]中存储的是最小边（i，j）的另一个端点i。在Prim算法执行过程中，先找出V-U中lowcost值最小的顶点j，然后根据数组closest选取边(j,closest[j］)，最后将j添加到U中，并对其他closest和lowcost作必要的修改。伪算法如下： int prim(Graph G, int u) { 1. u0= 起始点u; 2. for 每个结点v 3. 初始化距离数组Closest()和Lowcost() 4. for V-U中的顶点i 5. for 所有顶点j 6 k＝使Lowcost()最小的顶点 7. 将顶点k及边(k,closest(k))加入MST中 8. for 所有顶点j 9. if 原Lowcost(j)c(k,j) 10. {Lowcost(j)= c(k,j) 11. Clostest(j)=k } 12. return MST } 调试分析 a．调试过程中遇到的问题b．算法的时空分析 程序清单 1、图的建立程序： 作为图的数据结构. #includestdio.h #includectype.h #define MAXN 50 #define INFINITY 32767 typedef struct{ int Vnum;/*图的顶点数*/ int Arcs[MAXN][MAXN];/*邻接矩阵*/ }Graph;/*图的邻接矩阵存储法*/ int create_graph(Graph *p){/*图的创建,成功时返回非0值，失败时返回0*/ int i,j,n; int v1,v2,w; char c; printf(\nInput the vexnumber of graph:); scanf(%d,n); if(n1) return 0; p-Vnum=n; for(i=0;in;i++) for(j=0;jn;j++)