数据结构课程设计-图的遍历和生成树的求解实现.doc

1、 目 录摘 要3前 言4正 文51.问题描述：52.采用类C语言定义相关的数据类型53各模块流程图及伪码算法64函数的调用关系图85调试分析91.调试中遇到的问题及对问题的解决方法92.算法的时间复杂度和空间复杂度96.测试结果10参考文献14摘 要图是一种复杂的非线性数据结构，一个图G（Grah）由两个集合V和E构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历基本思路是假设从图中某顶点U出发，在访问了顶点U之后依次访问U的各个未访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问的顶点的领接点先于后访问的顶点被访问。直至所有领接点被访问到。深度优先的基本思

2、路是从某个顶点出发，访问此顶点，然后依次从V的未被访问的领接点出发深度优先检索土。直至图中所有顶点都被访问到。PRIM算法KRUSKAL算法；可以对图形进行最小生成树的求解。主要问题是：（1）当给出一个表达式时，如何创建图所表达的树，即相应的逻辑结构和存储结构？（2）表达式建立好以后，如何求出其遍历？深度优先和广度优先遍历。（3）计算它的最小生成树？主要是prim算法和kruscal算法两种形式。前 言很多涉及图的操作的算法都是以图的遍历操作为基础，通过遍历的演示，方便在学习中更好的理解突地遍历的过程。通过对图的深度优先遍历和广度优先遍历的演示，分别两种遍历的不同与其优缺点。我们在对一些问题进

3、行求解时，会发现有些问题很难找到规律，或者根本无规律可寻。对于这样的问题，可以利用计算机运算速度快的特点，先搜索查找所有可能出现的情况，再根据题目条件从所有可能的情况中，删除那些不符合条件的解。在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索， 本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展， 也就是说先产生 的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。很多问题都可以用广度优先搜索进行处理，如翻币问题、最短路径问题等。在计算机中，有多种方法存储图的信息，由于图的结构复杂，使用广泛，一般应根据实际的应用，选

4、择适合的表示方法。常用的图的存储结构有邻接矩阵、邻接多重表和邻接表。在实际问题当中，经常遇到这类问题，为新建的某个机构进行选址，道路交通路线，如何走完所有路线，旅游线路等一系列问题都涉及到图的知识。图是一种复杂的非线性数据结构，一个图G（Grah）由两个集合V和E。构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历基本思路是假设从图中某顶点U出发，在访问了顶点U之后依次访问U的各个未访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问的顶点的领接点先于后访问的顶点被访问。直至所有领接点被访问到。深度优先的基本思路是从某个顶点出发，访问此顶点，然后依次从V的未被

5、访问的领接点出发深度优先检索图。直至图中所有顶点都被访问到。PRIM算法KRUSKAL算法；可以对图形进行最小生成树的求解。树型结构是一种非线性结构，它用于描述数据元素之间层次关系，如人类社会的族谱等，树型结构的应用非常广泛，磁盘文件目录结构就是一个典型的例子。正 文1.问题描述：图是一种复杂的非线性数据结构，一个图G（Grah）由两个集合V和E构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历基本思路是假设从图中某顶点U出发，在访问了顶点U之后依次访问U的各个未访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问的顶点的领接点先于后访问的顶点被访问。直至所有

6、领接点被访问到。深度优先的基本思路是从某个顶点出发，访问此顶点，然后依次从V的未被访问的领接点出发深度优先检索土。直至图中所有顶点都被访问到。PRIM算法KRUSKAL算法；可以对图形进行最小生成树的求解。2.采用类c语言定义相关的数据类型#define int_max 10000 /定义邻接矩阵最大值10000为无穷大#define max 20 /最大顶点个数typedef struct /开始对 邻接表或图进行定义char vexs20; /顶点数的名称AdjMatrix arcs; /邻接矩阵 int vexnum,arcnum /图中顶点数和边数int creatMGraph_L(M

7、Graph_L &G)/创建图用邻接矩阵表示int visitedmax; /访问标记typedef struct arcnode /弧结点int adjvex; /该弧指向的顶点的位置，即边或弧依赖的顶点序号char *info; / 该弧信息char data; /结点信息基本操作：int creatadj(algraph &gra,MGraph_L G)/用邻接表存储图int initqueue(linkqueue &q)/初始化队列int enqueue(linkqueue &q,int e)/入队int dequeue(linkqueue &q,int &e)/出队int queue

8、empty(linkqueue q)/判断队为空void bfstra(algraph gra)/广度优先遍历int bfstra_fen(algraph gra)/求连通分量3各模块流程图及伪码算法int prim(int gmax,int n) /最小生成树PRIM算法int lowcostmax,prevexmax; /LOWCOST存储当前集合U分别到剩余结点的最短路径 /prevex存储最短路径在U中的结点int i,j,k,min; for(i=2;i=n;i+) /n个顶点，n-1条边 lowcosti=g1i; /初始化 prevexi=1; /顶点未加入到最小生成树中 low

9、cost1=0; /标志顶点1加入U集合 for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) /寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); lowcostk=0; /顶点k加入U for(j=2;j=n;j+) /修改由顶点k到其他顶点边的权值 if(gkj0) f=acrvisitedf;return f;void kruscal_arc(MGraph

10、_L G,algraph gra) edg edgs20;int i,j,k=0;for(i=0;i!=G.vexnum;+i) for(j=i;j!=G.vexnum;+j) if(G.arcsij.adj!=10000) edgsk.pre=i; edgsk.bak=j; edgsk.weight=G.arcsij.adj; +k; int x,y,m,n;int buf,edf;for(i=0;i!=gra.arcnum;+i) acrvisitedi=0; for(j=0;j!=G.arcnum;+j) m=10000; for(i=0;i!=G.arcnum;+i) if(edgsi

11、.weightm) m=edgsi.weight; x=edgsi.pre; y=edgsi.bak; n=i; / coutxym;/ coutendl; buf=find(acrvisited,x); edf=find(acrvisited,y); / coutbuf edfendl; edgsn.weight=10000; if(buf!=edf) acrvisitedbuf=edf; cout(x,y)m; coutendl; 4函数的调用关系图函数调用关系如图4.1所示图4.1 函数调用关系图5调试分析1.调试中遇到的问题及对问题的解决方法解决Visual C+ 6.0不正确连接的问

12、题明明改动了一个文件，却要把整个项目全部重新编译链接一次。刚刚链接好，一运行，又提示重新编译链接一次。这是因为出现了未来文件(修改时间和创建时间比系统时间晚)的缘故。可以这样处理：找到工程文件夹下的debug目录，将创建和修改时间都比系统时间的文件全部删除，然后再从新“Rebuild All”一次。2.算法的时间复杂度和空间复杂度关于时间复杂度的计算是按照运算次数来进行的, 关于空间复杂度的计算是在程序运行过程所要借助的内容空间大小。即：空间复杂是储存空间的大小和变换等等决定的.时间复杂是逻辑比较、赋值等基本运算的次数决定的.prim算法的时间复杂度为O（n 2）,kruskcal算法的时间复

13、杂度为O（eloge）prim的空间复杂度为O（n* prevex）, kruskcal算法的空间复杂度为O（n）6.测试结果(1）输入图的顶点即弧度个数：(2)分别写出边的权值：邻接矩阵和邻接表创建成功，显示出菜单：菜单选择：输入0，显示邻接矩阵输出y 进行下一步操作，重新选择菜单，输出1显示邻接表：输出y 进行下一步操作，重新选择菜单，输出2显示广度优先遍历：输出y 进行下一步操作，重新选择菜单，输出3显示深度优先遍历：输出y 进行下一步操作，重新选择菜单，输出4，显示prim算法计算最小生成树：输出y 进行下一步操作，重新选择菜单，输出5，显示kruscal算法计算最小生成树：输出y 进

14、行下一步操作，重新选择菜单，输出6,计算出该图的连通分量：输出n，结束操作，退出运行: 设计总结在这三周的算法与数据结构课程设计中,我的题目是:图的遍历和生成树的求解实现,这三周课程设计中,通过该题目的设计过程,我加深了对图数据结构及队列的逻辑结构,存储结构及图的深度优先和广度优先遍历过程,Prim算法和Kruscal算法进行最小生成树求解过程的理解,对图数据结构上基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。一个人要完成所有的工作是非常困难和耗时的。在以后的学习中我会更加注意各个方面的能力的协调发展。在课程设

15、计时遇到了很多的问题，在老师的帮助，和对各种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。三周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织，来配合学习，三周中我收益很 大，学到很多。致 谢在本次算法与数据结构的课程设计中，我学到了很多的东西，同时也得到了很多人的帮助和指导。在此我非常的感谢他们，感谢他们这些天对我的帮助、感谢他们对我的悉心指导。其次，我更要感谢我们的指导老师王旭阳老师。谢谢她这三周以来对我

16、们的悉心指导和帮助。感谢她能在百忙中抽出时间，在机房高温之下还非常认真的为我们做课设指导，在此，我深深的感谢我的指导老师。最后，我还要感谢我们的学校以及学校领导，感谢他们能够给我们一个这么好的锻炼平台，让我们能够对自己所学的知识充分的利用和学习，让我的个人能力也有所提高。参考文献1. 严蔚敏，吴伟民， 数据结构（C语言版），北京：清华大学出版社，20032. 严蔚敏，吴伟民， 数据结构题集（C语言版），北京：清华大学出版社，20053. DATA STRUCTURE WITH C+，William Ford，William Tcpp，北京：清华大学出版社（影印版），20054. 谭浩强，C语言

17、程序设计，北京：清华大学出版社，2005附录 原程序(带注释)#include #include #includeusing namespace std;#define int_max 10000#define inf 9999#define max 20/邻接矩阵定义typedef struct ArcCellint adj;char *info;ArcCell,AdjMatrix2020;typedef structchar vexs20;AdjMatrix arcs;int vexnum,arcnum;MGraph_L;/int localvex(MGraph_L G,char v)/返

18、回V的位置int i=0;while(G.vexsi!=v)+i;return i;int creatMGraph_L(MGraph_L &G)/创建图用邻接矩阵表示n括号ofstream fout(out.doc,ios:out);char v1,v2;int i,j,w;cout创建无向图endl请输入图G顶点和弧的个数:(5 7)不包括()G.vexnumG.arcnum;foutG.vexnum G.arcnumn;for(i=0;i!=G.vexnum;+i)cout输入顶点iG.vexsi;foutG.vexsi ;for(i=0;i!=G.vexnum;+i)for(j=0;j!

19、=G.vexnum;+j)G.arcsij.adj=int_max;G.arcsij.info=NULL;for(int k=0;k!=G.arcnum;+k)cout输入一条边依附的顶点和权:(a b 3)不包括()v1v2w;/输入一条边依附的两点及权值foutendl;foutv1 v2 w;i=localvex(G,v1);/确定顶点V1和V2在图中的位置j=localvex(G,v2);G.arcsij.adj=w;G.arcsji.adj=w;cout图G邻接矩阵创建成功！endl;fout.close();return G.vexnum;void ljjzprint(MGraph

20、_L G)int i,j;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)coutG.arcsij.adj ;coutadjvex=j;gra.verticesi.firstarc=arc;arc-nextarc=NULL;p=arc;+j;while(G.arcsij.adj!=int_max&j!=G.vexnum)tem=(arcnode *)malloc(sizeof(arcnode);tem-adjvex=j;gra.verticesi.firstarc=tem;tem-nextarc=arc;arc=tem;+j;-j;elseif(G.

21、arcsij.adj!=int_max&j!=G.vexnum)arc=(arcnode *)malloc(sizeof(arcnode);arc-adjvex=j;p-nextarc=arc;arc-nextarc=NULL;p=arc;gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;/*for(i=0;i!=gra.vexnum;+i)arcnode *p;couti ;p=gra.verticesi.firstarc;while(p!=NULL)coutadjvex;p=p-nextarc;coutendl;*/cout图G邻接表创建成功！endl;ret

22、urn 1;void adjprint(algraph gra)int i;for(i=0;i!=gra.vexnum;+i)arcnode *p;couti ;p=gra.verticesi.firstarc;while(p!=NULL)coutadjvex;p=p-nextarc;coutadjvex;int nextadjvex(algraph gra,vnode v,int w)/返回依附顶点V的相对于W的下一个顶点arcnode *p;p=v.firstarc;while(p!=NULL&p-adjvex!=w)p=p-nextarc;if(p-adjvex=w&p-nextarc!

23、=NULL)p=p-nextarc;return p-adjvex;if(p-adjvex=w&p-nextarc=NULL)return -10;int initqueue(linkqueue &q)/初始化队列q.rear=(queueptr)malloc(sizeof(qnode);q.front=q.rear;if(!q.front)return 0;q.front-next=NULL;return 1;int enqueue(linkqueue &q,int e)/入队queueptr p;p=(queueptr)malloc(sizeof(qnode);if(!p)return 0

24、;p-data=e;p-next=NULL;q.rear-next=p;q.rear=p;return 1;int dequeue(linkqueue &q,int &e)/出队queueptr p;if(q.front=q.rear)return 0;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear=p)q.rear=q.front;free(p);return 1;int queueempty(linkqueue q)/判断队为空if(q.front=q.rear)return 1;return 0;void bfstra(algr

25、aph gra)/广度优先遍历int i,e;linkqueue q;for(i=0;i!=gra.vexnum;+i)visitedi=0;initqueue(q);for(i=0;i!=gra.vexnum;+i)if(!visitedi) visitedi=1;coutgra.verticesi.data;enqueue(q,i);while(!queueempty(q)dequeue(q,e);/ cout e=0;we=nextadjvex(gra,gra.verticese,we)if(!visitedwe)visitedwe=1;coutgra.verticeswe.data;e

26、nqueue(q,we);int dfs(algraph gra,int i);/声明DFSint dfstra(algraph gra)int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)dfs(gra,j);return 0;int dfs(algraph gra,int i)visitedi=1;int we1;/ coutivisitediendl;coutgra.verticesi.data;/ cout=0;we=nextadjvex(gra,gra.verticesi

27、,we)/ coutwevisitedweendl;we1=we;/ coutnextadjvex(gra,gra.verticesi,we)endl;if(visitedwe=0)/ coutdfs(gra,we);/endl;/ coutiwe1endl;we=we1;/ coutnextadjvex(gra,gra.verticesi,we)endl;return 12;int bfstra_fen(algraph gra)/求连通分量int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visit

28、edj=0)dfs(gra,j);coutendl;return 0;typedef structint adjvex;int lowcost;closedge;/*int minimum(closedge *p);int minispantree(MGraph_L G,char u)int k,j,i;closedge closedge_a20;k=localvex(G,u);/ coutkendl;for(j=0;j!=G.vexnum;+j)if(j!=k)closedge_aj.adjvex=u;closedge_aj.lowcost=G.arcskj.adj;for(i=1;i!=G

29、.vexnum;+i)k=minimum(closedge_a);coutk;coutclosedge_ak.adjvex G.vexskendl;closedge_ak.lowcost=0;for(j=0;j!=G.vexnum;+j)if(G.arcskj.adjp-lowcost)s=p-lowcost;return s;*/int prim(int gmax,int n) /最小生成树PRIM算法int lowcostmax,prevexmax; /LOWCOST存储当前集合U分别到剩余结点的最短路径/prevex存储最短路径在U中的结点int i,j,k,min;for(i=2;i=

30、n;i+) /n个顶点，n-1条边lowcosti=g1i; /初始化prevexi=1; /顶点未加入到最小生成树中lowcost1=0; /标志顶点1加入U集合for(i=2;i=n;i+) /形成n-1条边的生成树min=inf;k=0;for(j=2;j=n;j+) /寻找满足边的一个顶点在U,另一个顶点在V的最小边if(lowcostjmin)&(lowcostj!=0)min=lowcostj;k=j;printf(%d,%d)%dt,prevexk-1,k-1,min);lowcostk=0; /顶点k加入Ufor(j=2;j=n;j+) /修改由顶点k到其他顶点边的权值if(g

31、kj0)f=acrvisitedf;return f;void kruscal_arc(MGraph_L G,algraph gra)edg edgs20;int i,j,k=0;for(i=0;i!=G.vexnum;+i)for(j=i;j!=G.vexnum;+j)if(G.arcsij.adj!=10000)edgsk.pre=i;edgsk.bak=j;edgsk.weight=G.arcsij.adj;+k;int x,y,m,n;int buf,edf;for(i=0;i!=gra.arcnum;+i)acrvisitedi=0;for(j=0;j!=G.arcnum;+j)m=

32、10000;for(i=0;i!=G.arcnum;+i)if(edgsi.weightm)m=edgsi.weight;x=edgsi.pre;y=edgsi.bak;n=i;/ coutxym;/ coutendl;buf=find(acrvisited,x);edf=find(acrvisited,y);/ coutbuf edfendl;edgsn.weight=10000;if(buf!=edf)acrvisitedbuf=edf;cout(x,y)m;coutendl;void main()algraph gra;MGraph_L G;int i,d,g2020;char a=a;

33、d=creatMGraph_L(G);creatadj(gra,G);vnode v;coutendl#注意：若该图为非强连通图(含有多个连通分量)时endl 最小生成树不存在,则显示为非法值。endlendl;cout菜单endlendl;cout0、显示该图的邻接矩阵endl;cout1、显示该图的邻接表endl;cout2、深度优先遍历endl;cout3、广度优先遍历endl;cout4、最小生成树PRIM算法endl;cout5、最小生成树KRUSCAL算法endl;cout6、该图的连通分量endlendl;int s;char y=y;while(y=y)cout请选择菜单：s;switch(s)case 0:cout邻接矩阵显示如下：endl;ljjzprint(G);break;case 1:cout邻接表显示如下：endl;adjprint(gra);break;case 2:cout广度优先遍历：;bfstra(gra);coutendl;break;case 3:for(i=0;i!=gra.vexnum;+i)visitedi=0;cout深度优先遍历：;dfstra(gra);coutendl;break;case 4:for(i=0;i!=G.vexnum;+i)for(int j=0;j!=G.vexnum;+