图的遍历和生成树求解实现 课程设计报告.docx

《图的遍历和生成树求解实现 课程设计报告.docx》由会员分享，可在线阅读，更多相关《图的遍历和生成树求解实现 课程设计报告.docx（21页珍藏版）》请在第一文库网上搜索。

1、中北大学数据结构课程设计说明书学生姓名：郭燕文学号：1021011720学院：软件学院专业：软件工程题目：图的遍历和生成树求解实现成绩指导教师尹四清、薛海丽2011年12月19日1设计目的:数据结构课程主要介绍最常用的数据结构,阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

2、训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。2设计内容和要求设计内容：(1)采用合适的存储结构来创建图，并实现图的遍历；(2)计算图的最小生成树，求联通分量设计要求：(1)先任意创建一个图；(2)图的DFS,BFS的递归和非递归算法的实现(3)展小生成树(两个算法)的实现，求连通分量的实现(4)要求用邻接矩阵、邻接表、十字链表多种结构存储实现3.本设计所采用的数据结构：本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。4.1详细设计思想这次课程设计我们主要是应用以前学习的数据结

3、构与面向对象程序设计知识,结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和卜字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。4.3核心代码#inc1udeinc1udeusingnamespacestd;defineint_max10000defineinf9999Jtde

4、finemax20/邻接矩阵定义typedefstructArcCe1122(intadj;char*info:ArcCe11,AdjMatrix2020;typedefstructcharvexs20;AdjMatrixarcs;intvexnum,arcnm;有向图的当前顶点数和弧数MGraphJ1;/intIoca1vex(MGraph_1G,charV)返回V的位置inti=0;whi1e(G.vexsi!=v)+i；returni;intcreatMGraph_1(MGraph_1&G)创建图用邻接矩阵表示charv1,v2;inti,j,w;coutC创建无向图end1请输入图G顶

5、点和弧的个数：(46)不包括G.vcxnumG.arcnum;for(i=0ji!=G.vcxnumj+i)cout输入顶点iG.vexsi;for(i=0ji!=G.vexnum;+i)for(j-0;j!=G.vexnum:+j)G.arcsij.adj=int_max;G.arcsij.info=NU11;for(intk=0;k!=G.arcnum;+k)COUt输入一条边依附的顶点和权：(ab3)不包括v1v2w;输入一条边依附的两点及权值i=1oca1vex(G,v1);确定顶点V1和V2在图中的位置j=1oca1vex(G,v2):G.arcsij.adj=w:G.arcsji.

6、adj=w;)COUt”图G邻接矩阵创建成功！end1;returnG.vexnm:voidIjjzprint(MGraph_1G)inti,j;for(i=0ji!=G.VeXnUm;+i)(for(j=0;j!=G.vexnumj+j)coutG.arcsij.adj*;coutadjvex=j;gra.verticesi.firstarc=arc;arc-nextarc=NU11;p=arc;+j;whi1e(G.arcsij.adj!=int_max&j!=G.vexnum)tem=(arcnode*)ma1Ioc(sizeof(arcnode);tem-adjvex=j;gra,ve

7、rticesi.firstarc=tem;tem-nextarc=arc;arc=tem:+j；J；)e1seif(G.arcsij.adj!=int_max&j!=G.vexnum)(arc=(arcnode*)ma11oc(sizeof(arcnode);p-nextarc=arc;arc-nextarc=NU11;p=arc;)gra.VeXnUm=G.vexnum;gra.arcnum=G.arcnum;/*for(i=0ji!=gra.vexnumj+i)arcnode*p:couti*;p=gra.verticesi.firstare;whi1e(p!=NU1Dcoutadjvex

8、:p=p-nextarc;coutend1;*/CoUt”图G邻接表创建成功！end1;return1;voidadjprint(a1graphgra)inti;for(i=0ji!=gra.vcxnumj+i)arcnode*p;couti*;p=gra.verticesi.firstare;Whi1e(P!=NU11)coutadjvex;p=p-nextarc;coutadjvex;intnextadjvex(a1graphgra,vnodev,intW)返回依附顶点V的相对于W的下一个顶点arcnode*p;p=v.firstarc:whi1e(p!=NU11&p-adjvex!=W)

9、p=p-nextarc:if(p-adjvex=wp-nextarc!=NU11)p=p-nextarc;returnp-adjvex;if(p-adjvex=wMp-nextarc=NU11)return-10;intinitquee(1inkquee&q)初始化队列q.rear=(queueptr)ma1Ioc(sizeof(qnode);q.front=q.rear;if(!q.front)return0;q.front-next=NU11;return1;intenqueue(1inkquee&q,inte)/入队queueptrp;P=(queueptr)ma11oc(sizeof(

10、qnode);if(!p)return0;p-data=e;p-next=NU11;q.rear-next=p;q.rear=p;return1;intdequeue(1inkqueue&q,int&e)出队queueptrp;if(q.front=q.rear)return0;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear=p)q.rear=q.front;free(p);return1;intqueueempty(1inkqueucq)判断队为空if(q.front=q.rear)return1;return0:voidbfstra(a1graphgra)广度优先遍历inti,e;1inkqueueq;for(i=0ji!=gra,vcxnumj+i)visitedi=O;initqueue(q):for(i=0;i!=gra.vcxnmj+i)if(!visitedi)visitedi=1;coutgra.verticesi.data;enqueue(q,i):whi