小生成树课程设计.doc

中北大学数据结构与算法课程设计说 明 书学 院、系：软件学院专 业：软件工程学 生 姓 名：xx学 号：xxx设 计 题 目：最小生成树问题 起 迄 日 期:2013年12月9日- 2013年12月20日指 导 教 师:李波2013 年12月 20 日1 需求分析 设计内容：给定一个地区的n个城市间的距离网，用prim算法或kruskal算法建立最小生成树，并计算得到的最小生成树的代价。 基本要求：（1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价；（2）表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）；（3）最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。 2本设计所采用的数据结构 本程序设计所采用的数据结构为图。3 设计思想 普里姆算法4 核心代码int main() /主函数 mgraph g; vertextype u; int k; createUDN(&g); /* 生成邻接矩阵结构的图 */ printf(nThe graph is:n); print(g); /*输出邻接矩阵*/ printf(input the city you want to start:); scanf(%s,u); /* 输入最小生成树的起点 */ k=locatedvex(g,u); while(k=-1) printf(the name of the city is wrong!n); printf(input the city you want to start again:); scanf(%s,u); k=locatedvex(g,u); minispantree(g,u); /* 普里姆算法求最小生成树 */ 4 代码#includestdio.h#includestring.h#define maxnum 20 /* 图的最大顶点数 */#define INFINITY 1000 /* 定义一个权值的最大值 */typedef char vertextype20; /*定义城市名称*/typedef struct arccellint adj; /*弧的权值*/int *info; /*弧上相关信息的指针*/arccell;typedef struct arrayvertextype adjvex; /*顶点的邻接点*/int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */array;typedef struct vertextype vexsmaxnum; /*顶点向量*/arccell arcsmaxnummaxnum; /*邻接矩阵*/int vexnum,arcnum; /*图的顶点个数和弧个数*/array closedgemaxnum; /* 用普里姆算法求最小生成树时的辅助数组 */ mgraph;void createUDN(mgraph *g) /* 用邻接矩阵构造n个城市间的距离网g */int i,j,m,n,k,a,b,c;vertextype x,y;printf(input the number of cities (at least 6 cities) :); scanf(%d,&g-vexnum); /* 输入城市的个数（图的顶点数） */printf(input the number of roads (at least 10 roads):);scanf(%d,&g-arcnum); /* 输入道路的边数（图的边数） */printf(input the name of %d cities :,g-vexnum);for(i=0;ivexnum;i+) scanf(%s,g-vexsi); /* 输入城市名称（图的顶点） */for(m=0;mvexnum;m+)for(n=0;nvexnum;n+)g-arcsmn.adj=INFINITY; /* 初始化邻接矩阵 */for(k=0;karcnum;k+)printf(input the distance of a road :);scanf(%s%s%d,x,y,&c); /* 输入城市间的距离（图中边的起点和终点及权值） */a=locatedvex(*g,x);b=locatedvex(*g,y);while(a=-1|b=-1)printf(the name of the city is wrong!n);printf(input the distance of a road again :);scanf(%s%s%d,x,y,&c); a=locatedvex(*g,x);b=locatedvex(*g,y);g-arcsab.adj=c;g-arcsba=g-arcsab;void print(mgraph g) /*输出用邻接矩阵构造的n个城市间距离网g*/ int i,j; for (i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) printf(%-4d ,g.arcsij.adj); printf(n); void minispantree(mgraph g,vertextype x) /* 从第k个顶点出发构造图g的最小生成树 */int i,j,t,k,sum=0;k=locatedvex(g,x);for(j=0;jg.vexnum;j+) /*辅助数组初始化*/if(j!=k) g.closedgej.lowcost=g.arcskj.adj; strcpy(g.closedgej.adjvex,x); g.closedgek.lowcost=0; /* 初始，U=u */for(i=1;ivexnum-1个顶点 */k=min(g); /* 求出生成树的下一个顶点 */printf(%s,%s) %dn,g.closedgek.adjvex,g.vexsk,g.closedgek.lowcost); /* 输出生成树的边和权值 */sum+=g.closedgek.lowcost; /*计算最小生成树的代价*/ g.closedgek.lowcost=0; /* 第k顶点并入U集 */ for(t=0;tg.vexnum;t+) /* 新顶点并入U后，修改辅助数组*/ if(g.arcskt.adjg.closedget.lowcost)strcpy(g.closedget.adjvex,g.vexsk);g.closedget.lowcost=g.arcskt.adj;printf(The shortest distance is %dn,sum); /*输出最小生成树的代价*/int min(mgraph g) /* 在辅助数组g.closedgei中选择权值最小的顶点，并返回其位置 */int i,a=0,min;min=maxnum;for(i=1;ig.vexnum;i+)if(g.closedgei.lowcostmin&g.closedgei.lowcost!=0)a=i;min=g.closedgei.lowcost; return a;int locatedvex(mgraph g,vertextype u) /*确定任一城市在距离网g中的位置*/int i;for(i=0;ig.vexnum;i+) if(strcmp(u,g.vexsi)=0) return i; return -1; int main() mgraph g; vertextype u; int k; createUDN(&g); /* 生成邻接矩阵结构的图 */ printf(nThe graph is:n); print(g); /*输出邻接矩阵*/ printf(input the city you want to start:); scanf(%s,u); /* 输入最小生成树的起点 */ k=locatedvex(g,u); while(k=-1) printf(the name of the city is wrong!n); printf(input the city you want to start again:); scanf(%s,u); k=locatedvex(g,u); minispantree(g,u); /* 普里姆算法求最小生成树 */5 程序运行结果 8 心得体会 本次课程设计我们经历了最短时间最繁重的设计任务，作为两人组的课程设计任务难度相对来说较大，我和我的合作伙伴尽了最