最小生成树课程设计

1、中北大学数据结构与算法课程设计说 明 书 学 院、系：软件学院专 业：软件工程学 生 姓 名：xx学 号：xxx设 计 题 目：最小生成树问题 起 迄 日 期:2013年12月9日- 2013年12月20日指 导 教 师:李波   2013 年12月 20 日1 需求分析 设计内容：给定一个地区的n个城市间的距离网，用prim算法或kruskal算法建立最小生成树，并计算得到的最小生成树的代价。 基本要求：（1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要

2、求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价；（2）表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）；（3）最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。 2本设计所采用的数据结构 本程序设计所采用的数据结构为图。3 设计思想 普里姆算法4 核心代码int main() /主函数 mgraph g; vertextype u; int k; createUDN(&g); /* 生成邻接矩阵结构的图 */ printf("nThe graph is:n"); print(g); /*输出邻接矩阵*/ pri

3、ntf("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、; /* 普里姆算法求最小生成树 */ 4 代码#include"stdio.h"#include"string.h"#define maxnum 20 /* 图的最大顶点数 */#define INFINITY 1000 /* 定义一个权值的最大值 */typedef char vertextype20; /*定义城市名称*/typedef struct arccellint adj; /*弧的权值*/int *info; /*弧上相关信息的指针*/arccell;typedef struct arrayvertextype adjvex; /*顶点的

5、邻接点*/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

6、 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 cit

7、ies :",g->vexnum);for(i=0;i<g->vexnum;i+) scanf("%s",g->vexsi); /* 输入城市名称（图的顶点） */for(m=0;m<g->vexnum;m+)for(n=0;n<g->vexnum;n+)g->arcsmn.adj=INFINITY; /* 初始化邻接矩阵 */for(k=0;k<g->arcnum;k+)printf("input the distance of a road :");scanf("%

8、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->ar

9、csab.adj=c;g->arcsba=g->arcsab;void print(mgraph g) /*输出用邻接矩阵构造的n个城市间距离网g*/ int i,j; for (i=0;i<g.vexnum;i+) for(j=0;j<g.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=locatedv

10、ex(g,x);for(j=0;j<g.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;i<g.vexnum;i+) /* 选择其余的G->vexnum-1个顶点 */k=min(g); /* 求出生成树的下一个顶点 */printf("(%s,%s) %dn",g.closedgek.adjvex,g.vexsk,g.closed

11、gek.lowcost); /* 输出生成树的边和权值 */sum+=g.closedgek.lowcost; /*计算最小生成树的代价*/ g.closedgek.lowcost=0; /* 第k顶点并入U集 */ for(t=0;t<g.vexnum;t+) /* 新顶点并入U后，修改辅助数组*/ if(g.arcskt.adj<g.closedget.lowcost)strcpy(g.closedget.adjvex,g.vexsk);g.closedget.lowcost=g.arcskt.adj;printf("The shortest distance is

12、%dn",sum); /*输出最小生成树的代价*/int min(mgraph g) /* 在辅助数组g.closedgei中选择权值最小的顶点，并返回其位置 */int i,a=0,min;min=maxnum;for(i=1;i<g.vexnum;i+)if(g.closedgei.lowcost<min&&g.closedgei.lowcost!=0)a=i;min=g.closedgei.lowcost; return a;int locatedvex(mgraph g,vertextype u) /*确定任一城市在距离网g中的位置*/int i;

13、for(i=0;i<g.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 心得体会 本次课程设计我们经历了最短时间最繁重的设计任务，作为两人组