普里姆算法生成最小生成树课程设计.doc

JINGCHU UNIVERSITY OF TECHNOLOGY数据结构（C语言描述）课程设计学 院 计算机工程学院 班 级 12级软件技术1班 学 号 2012304040122、120 124、133、121 学生姓名 周鑫、王彬彬、李松平 张圣玮、魏远迎 指导教师 余云霞 2014年 1月3日目 录1 课程设计介绍11.1 课程设计内容11.2 课程设计要求12 课程设计原理22.1 课设题目粗略分析22.2 原理图介绍32.2.1 功能模块图32.2.2 流程图分析33 数据结构分析103.1 存储结构103.2 算法描述124 调试与分析224.1 调试过程224.2程序执行过程22参考文献28附 录28 1 课程设计介绍1.1 课程设计内容 编写算法能够建立带权图，并能够用Prim算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。1.2 课程设计要求1. 可以输入顶点、边数及各路径的权值；2. 通过建立无向图或有向图能过输出邻接矩阵或邻接表；3. 可以输出建立的最小生成树；4. 画出流程图，且函数有必要说明、注释；5. 课设完成后上交报告及核心代码。2 课程设计原理2.1 课设题目粗略分析根据课设题目要求，拟将整体程序分为两大模块。以下是两个模块的大体分析：1. 创建网图并确定网图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用邻接表和邻接矩阵（起点、终点和权值）两种存储结构，方便以后的编程。2.Prim算法。设置两个新的集合U和T，其中U用于存放带权图G的最小生成树的结点的集合，T用于存放带权图G的最小生成树边的权值的集合。其思想是：令集合U的初值为Uu0（即假设构造最小生成树时从结点u0开始），集合T 的初值为T=。从所有结点u属于U和结点v属于V但不属于U的带权边中选出具有最小权值的边（u，v），将结点v加入集合U中，将边（u，v）加入集合T中。如此不断重复，当U=V时，最小生成树便构造完毕。2.2 原理图介绍2.2.1 功能模块图显示菜单进行选择选择创建（有）无向图及存储方式有向图邻接矩阵无向图邻接矩阵有向图邻接表无向图邻接表调用普里姆算法输出最小生成树结束开始图2.1 功能模块图 2.2.2 流程图分析1. 主函数开始显示菜单，选择输入1或2选择1选择2 调用createAgraph()函数结束选择1调用CreateGraph()函数选择2调用CreateMGraph()函数调用createALgraph()函数调用Prim函数，输出最小生成树 图2.2 主函数流程图2. CreateMGraph()函数开始int i,j,kfor(i=0;i<G->n;i+)scanf(“n%c”,&(G->vexsi);for(i=0;i<G->n;i+)for(j=0;i<G->n;i+)i=jG->edgesij=0;YNG->edgesij=max;for (k=0;k<G->e;k+)scanf("n%d,%d,%d",&i,&j,&weight);G->edgesij=weight;OutPut(G);prim(G->edges,G->n,G->vexs);结束 图2.3 CreateMGraph()函数流程图3Prim()函数开始int i,j,k,lowcost100,mincost;for(i=1;i<n;i+) lowcosti=gm0i;closevertexi=0; seti=0; i=1; j=1;YYlowcost0=0;closevertex0=0;for(i=1;i<n;i+)mincost=max;j=1;k=1;j<nlowcostj<mincost&&lowcostj!=0mincost=lowcostj;k=j;j+;NNprintf("顶点的序号=%d 边的权值=%dn",k,mincost); lowcostk=0; for(j=0;j<n;j+)gmkj<lowcostjlowcostj=gmkj; closevertexj=k;结束图2.4 Prim()函数流程图4. createALgraph()函数开始int i,j,k,w;edgenode *s;scanf("%d,%d%*c",&(g->n),&(g->e);for(i=0;i<g->n;i+)scanf("%d",&(g->adjlisti.vertex);g->adjlisti.firstedges=NULL;for(k=0;k<g->e;k+)scanf("%d,%d,%d",&i,&j,&w);s=(edgenode*)malloc(sizeof(edgenode);s->adjvex=j;s->weight=w;s->next=g->adjlisti.firstedges;g->adjlisti.firstedges=s;结束图2.5 createAgraph()函数流程图5. 邻接矩阵Output()输出函数开始int i,j;for (i=0;i<G->n;i+) printf("%d ",G->vexsi);for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)printf("t%d ",G->edgesij);结束图2.6 Output()函数流程图 3 数据结构分析3.1 存储结构定义邻接矩阵及邻接表的结构体（1）邻接矩阵#define MaxVertexNum 100#define max 1000typedef int VertexType;typedef int EdgeType;typedef struct VertexType vexsMaxVertexNum; EdgeType edgesMaxVertexNumMaxVertexNum; int n,e; MGraph;（2）邻接表#define MaxVertexNum 100typedef int vertextype;typedef struct node int adjvex; int weight; struct node *next; edgenode;typedef struct vnode vertextype vertex; edgenode *firstedges; vertexnode;typedef vertexnode AdjListMaxVertexNum;typedef struct AdjList adjlist; int n,e;ALgraph;(3) 邻接表转换成邻接矩阵辅助结构体typedef int edgetype ;typedef struct edgetype vexsMaxVertexNum; edgetype edgesMaxVertexNumMaxVertexNum; int n,e; graph; /*邻接表转换成邻接矩阵辅助结构体*/3.2 算法描述1. 创建有向网图邻接矩阵存储void CreateMGraph(MGraph *G) int i,j,k,weight; printf("t=有向网图邻接矩阵=n");printf("请输入顶点数和边数："); scanf("%d,%d",&(G->n),&(G->e); printf("请输入顶点信息:"); for (i=0;i<G->n;i+) scanf("n%d",&(G->vexsi); for (i=0;i<G->n;i+) for (j=0;j<G->n;j+) if(i=j) G->edgesij=0; else G->edgesij=max; /*初始化邻接矩阵*/ printf("输入边对应的两个顶点的序号及权值："); for (k=0;k<G->e;k+) scanf("n%d,%d,%d",&i,&j,&weight); G->edgesij=weight; printf("输出顶点信息及邻接矩阵:n" ); OutPut(G); printf("输出最小生成树的信息:n"); prim(G->edges,G->n,G->vexs);2. 创建无向网图邻接矩阵存储void CreateGraph(MGraph *G) int i,j,k,weight; printf("t=无向网图邻接矩阵=n"); printf("请输入顶点数和边数："); scanf("%d,%d",&(G->n),&(G->e); printf("请输入顶点信息:"); for (i=0;i<G->n;i+) scanf("n%d",&(G->vexsi); for (i=0;i<G->n;i+) for (j=0;j<G->n;j+) if(i=j) G->edgesij=0; else G->edgesij=max; /*初始化邻接矩阵*/ printf("输入边对应的两个顶点的序号及权值："); for (k=0;k<G->e;k+) scanf("n%d,%d,%d",&i,&j,&weight); G->edgesij=weight; G->edgesji=weight; printf("输出顶点信息及邻接矩阵:n" ); OutPut(G); printf("输出最小生成树的信息:n"); prim(G->edges,G->n,G->vexs); 3. 创建有向网图邻接表存储void createAgraph( ALgraph *g) /*创建有向网图*/ int i,j,k,w; edgenode *s; printf("t=有向网图邻接表=n"); printf("输入顶点数和边数:"); scanf("%d,%d%*c",&(g->n),&(g->e); printf("n输入顶点:"); for(i=0;i<g->n;i+) scanf("%d",&(g->adjlisti.vertex); g->adjlisti.firstedges=NULL; printf("n输入边和权值:"); for(k=0;k<g->e;k+) scanf("%d,%d,%d",&i,&j,&w); s=(edgenode*)malloc(sizeof(edgenode); s->adjvex=j; s->weight=w; s->next=g->adjlisti.firstedges; g->adjlisti.firstedges=s; DispAdjList(g);4. 创建无向网图邻接表存储void createALgraph(ALgraph *g) /*创建无向网图*/ int i,j,k,w; edgenode *s;printf("t=无向网图邻接表=n"); printf("输入顶点数和边数:"); scanf("%d,%d%*c",&(g->n),&(g->e); printf("n输入顶点:"); for(i=0;i<g->n;i+) scanf("%d",&(g->adjlisti.vertex); g->adjlisti.firstedges=NULL; printf("n输入边和权值:"); for(k=0;k<g->e;k+) scanf("%d,%d,%d",&i,&j,&w); s=(edgenode*)malloc(sizeof(edgenode); s->adjvex=j; s->weight=w; s->next=g->adjlisti.firstedges; g->adjlisti.firstedges=s; s=(edgenode*)malloc(sizeof(edgenode); s->adjvex=i; s->weight=w; s->next=g->adjlistj.firstedges; g->adjlistj.firstedges=s; DispAdjList(g);5.prim算法void prim(int gmMaxVertexNum ,int n,int closevertex ) /*普里姆算法*/ int lowcost100; int mincost; int i,j,k; for(i=0;i<n;i+) lowcosti=gm0i; closevertexi=0; lowcost0=0; closevertex0=0; for(i=1;i<n;i+) mincost=max; j=1; k=1; while(j<n) if(lowcostj<mincost&&lowcostj!=0) mincost=lowcostj; k=j; j+; printf("顶点的序号=%d 边的权值=%dn",k,mincost); lowcostk=0; for(j=0;j<n;j+) if(gmkj<lowcostj) lowcostj=gmkj; closevertexj=k; 6. 输出邻接矩阵存储函数void OutPut (MGraph *G) int i,j; printf("tE= "); for (i=0;i<G->n;i+) printf("%d ",G->vexsi); printf(""); printf("n"); for(i=0;i<G->n;i+) for(j=0;j<G->n;j+) printf("t%d ",G->edgesij); printf("n"); 7. 输出邻接表存储函数void DispAdjList(ALgraph *g) int i; edgenode *p; printf("n网图的邻接表表示如下：n"); for (i=0; i<g->n; i+) printf("%d,%3d=>",i,g->adjlisti.vertex); p=g->adjlisti.firstedges; while (p!=NULL) printf("(%d,%d)->",p->adjvex,p->weight); p=p->next; printf("n"); 8. 邻接表转换成邻接矩阵函数void change(ALgraph *g) /*邻接表转换成邻接矩阵*/ int i,j; edgenode *p; graph *M;M=(graph*)malloc(sizeof(graph); M->n=g->n; M->e=g->e; for(i=0;i<M->e;i+) for(j=0;j<M->e;j+) if(i=j)M->edgesij=0; else M->edgesij=MaxVertexNum; for(i=0;i<g->n;i+) M->vexsi=g->adjlisti.vertex; for(i=0;i<g->n;i+) p=g->adjlisti.firstedges; while(p) M->edgesip->adjvex=p->weight; p=p->next; prim(M->edges,M->n,M->vexs);4 调试与分析4.1 调试过程测试数据（对下图进行测试）：1右图是6个顶点的10条边的连通图六个顶点分别是：1 2 3 4 5 6顶点序号和边上的权植分别是0 1 110 2 150 3 181 2 331 4 122 3 202 4 222 5 253 5 274 5 2942365 4.2程序执行过程系统使用说明：1. 输入的数据可以是100以内的整数；2. 本系统可以建立带权图，并能够用Prim算法求该网图的最小生成树。 3. 该系统会有菜单提示，进行选项：4.程序实际运行截图（1）有向图邻接矩阵输出最小生成树截图：（2）无向图邻接矩阵输出最小生成树截图：（3） 有向图邻接表输出最小生成树截图：（4） 无向图邻接表输出最小生成树截图：参考文献（1）李素若，数据结构（C语言描述），2009，化学工业出版社 （2）严蔚敏、吴伟民，数据结构（C语言描述），1999，清华大学出版社 （3）徐孝凯，数据结构课程实验，2002，清华大学出版社 （4）孟佳娜、胡潇琨，算法与数据结构实验与习题，2004，机械工业出版社 附 录说明：本次课程设计由组长周鑫，组员王彬彬、李松平、张圣玮、魏远迎共同完成。其中邻接矩阵存储有向图、无向图及调用普里姆算法生成最小生成树、流程图绘制、任务书填写由王彬彬完成；邻接表存储有向图、无向图及调用普里姆算法生成最小生成树、菜单界面由周鑫完成；李松平、张圣玮、魏远迎主要负责文档排版，代码调试等综合应用。课程设计总结：本次课程设计涉及到的范围虽不广，但能够比较系统的对C语言和数据结构进行一次整理和复习。同时有了很多的体会和经验。1. 巩固了以前学过的C语言的知识，在这次课程设计中我体会到C语言超强的逻辑性，能够熟练使用VC+的编译环境，也对这两门课程有了新的认识，他们既有联系，又相互区别，在编写程序过程中要灵活应用2. 对数据结构的理解有待加强，算法的知识面也有待于提高。不同的人会选择不同的算法，所以即使同样的程序，不同的人必然会设计出不同的方案，所以以后的学习生活中，一定要广泛涉猎，掌握更多更好的解决问题的方法。3. 此次设计让我意识到程序设计是脑力劳动和体力劳动相结合的，没有平时基础的训练是不会写出高效的算法。4. 此次课程设计时间虽短，课设的过程是短暂的，但我所收获的是永恒的。它让我尝到了学习的快乐，成功的喜悦，更让我懂得了不少做人的道理。要完成一项任务或把东西学好就必须有足够的信心，持久的耐心，有面对困难无所畏惧的精神，这对我日后的学习和生活产生了深远的影响。指导教师评语：指导教师(签字)： 年 月 日课程设计成绩