图的遍历的数据结构课程设计.doc

图的深度遍历和广度遍历学生姓名： 指导老师：肖增良摘 要：数据结构是一门专业基础课，学习数据结构要求我们学会研究计算机加工的数据结构特性，以便为应用涉及的数据结构选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的的技术,图是应用最广泛的数学结构。图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现。关键词 图 遍历 深度 广度 队列 算法目 录1.课程设计的要求 32.设计方案 4 2.1图的初始化 42.2深度优先搜索的基本思想4 2.3广度优先搜索的基本思想 62.4图的深度优先搜索和广度优先搜索的定义 73.图的遍历模块化 83.1图的存储结构 83.2邻接表的定义和初始化 93.3BDF和DBF编码 10 4图的遍历流程图 134.2图的深度优先遍历流程134.2图的广度优先遍历流程图145系统运行运行环境与结果155.1运行环境155.2结构图图及运行结果166课程设计总结17参考文献18附录：源程序代码191课程设计的要求该课题要求我们熟悉图，图是一种较为线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每一个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其孩子结点）有关，但只能和上一层中一个元素（即双亲结点）有关；而在图形结构中，节点之间的的关系是任意的，图中任意两个数据元素之间都可能相关。图的应用极为广泛，特别是近年来的迅速发展，已经渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及其他的分支中。图的遍历算法是求解图的连通性问题、拓扑排序和求解关键路径等算法的基础。而深度遍历优先搜索和广度遍历优先搜索是遍历图的最基本的两条途径。因此，本课程要求我们能熟练地掌握深度优先搜索遍历和广度优先搜索遍历的方法对图进行搜索。 2设计方案2.1图的初始化typedef VertexNode AdjListMaxVertexNum; /*AdjList是邻接表类typedef struct node /*边表结点*/ int adjvex; /*邻接点域*/ struct node *next; /*链域*/EdgeNode;typedef struct vnode /*顶点表结点*/ char vertex; /*顶点域*/ EdgeNode *firstedge; /*边表头指针*/VertexNode;型*/typedef struct AdjList adjlist; /*邻接表*/ int n,e; /*图中当前顶点数和边数*/ ALGraph; /*图类型*/2.2深度优先搜索的基本思想深度优先搜索是一种递归的过程，正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。比如设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。其具体过程如下图所示图2.1 图的深度优先遍历(1)访问vo, 记录visited0=True, 从v0的一个未被访问过的邻接点v1出发进行遍历(2)访问v1, visited1=True,从v1的一个未被访问过的邻接点v4出发遍历(3)访问v4, visited4=True,从v4的一个未被访问过的邻接点v5出发遍历(4)访问v5, visited5=True,由于v5的两个邻接点v1和v4都被访问过，退回上一邻接点v4，又v4的两个邻接点v1和v5都被访问过，再退回上一邻接点v1,从未被访问过邻接点V6出发遍历(5)访问v6, visited6=True,从v6的一个未被访问过的邻接点v2出发遍历(6)访问v2, visited2=True,v2所有邻接点都访问过，退回上一顶点v6,同理，v6退回v1,v1退回v0,再从v0未被访问过邻接点v3出发遍历(7)访问v3, visited3=True，退回v0,因所有邻接点都访问过，再退回，结束图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。2.3广度优先搜索的基本思想首先访问图中指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、 Vk，并均标记为已访问过，然后再按照Vj、Vk的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止，其具体过程如下图所示图2.2 图的广度优先遍历(1)访问v0,visited0=True (2)访问v0所有未访问过邻接v1和v2, visited1=True, visited2=True;(3)访问v1所有未被访问过的邻接点v3和v4,v5,并将它们标记已访问过；(4)访问v2所有未被访问过的邻接点v6, visited6=True；(5)访问v3所有未被访问过的邻接点v7, visited7=True；(6)访问v4所有未被访问过的邻接点(无)(7)访问v5所有未被访问过的邻接点v8, visited8=True；(8)访问v6所有未被访问过的邻接点(无)；(9)依次访问v7，v8所有未被访问过的邻接点(无)，结束。在广度优先搜索中，若对顶点V1的访问先于顶点V2的访问，则对V1邻接顶点的访问也先于V2邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。设此队列由一个一维数组构成，数组名Queue，队首指针和队尾指针分别为front和rear。假设数组足够大，不必考虑有溢出的可能性。广度优先搜索不是递归过程，不能用递归形式。2.4图的深度优先搜索和广度优先搜索的定义深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图，在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续下去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。图的广度优先搜索是首先访问图中指定的起始点Vi，并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、 Vk，并均标记为已访问过，然后再按照Vj、Vk的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止3图的遍历模块化3.1图的存储结构对图中每个顶点建立一个单链表;第i个单链表中的头结点用以存放第i个顶点的值Vi,其后的结点的adjvex域中存放的序号j表示图中第j个顶点Vj是顶点Vi的第一个邻接点(对有向图来说表示以Vi为弧尾以Vj为弧头的弧);链表中的再下一个结点中的adjvex中存放的序号k表示图中第k个顶点Vk是顶点Vi的再下一个邻接点，以此类推。其具体方法如下图所示 ABDC 0213 图3.1 图的存储结构datataafirstarcadjvexnextarcadjvexnextarcA21B3C0D0123图3.1 图的存储结构3.2邻接表的定义和初始化临接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧)。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点。每个链表上附设一个表的结点，在表结点中，除了设有链域（firstarc）指向链表中的结点外，还设有存储顶点vi，的名或其他有关的信息的数据域（data）。adjvexnextarc图3.2邻接表的定义datafirstarc图3.2 邻接表的定义void CreatALGraph(ALGraph *G) int i,j,k; char a; EdgeNode *s; /*定义边表结点*/ printf(Input VertexNum(n) and EdgesNum(e): ); scanf(%d,%d,&G-n,&G-e); /*读入顶点数和边数*/ scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) /*建立边表*/ scanf(%c,&a); G-adjlisti.vertex=a; /*读入顶点信息*/ G-adjlisti.firstedge=NULL; /*边表置为空表*/ printf(Input edges,Creat Adjacency Listn); for(k=0;ke;k+) /*建立边表*/ scanf(%d%d,&i,&j); /*读入边（Vi，Vj）的顶点对序号*/ s=(EdgeNode *)malloc(sizeof(EdgeNode); /*/生成边表结点*/ s-adjvex=j; /*邻接点序号为j*/s-next=G-adjlisti.firstedge; G-adjlisti.firstedge=s; /*将新结点*S插入顶点Vi的边表头部*/ s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; /*邻接点序号为i*/ s-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; /*将新结点*S插入顶点Vj的边表头部*/ 3.3 BFS和DFS编码 /*BFS编码*/void BFSM(MGraph *G，int k) 以vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i，j； CirQueue Q； InitQueue(&Q)； printf(visit vertex：c，G-vexsk)； /访问源点vk visitedk=TRUE； EnQueue(&Q，k)； while(!QueueEmpty(&Q) i=DeQueue(&Q)； /vi出队 for(j=0;jn;j+)/依次搜索vi的邻接点vj if(G-edgesij=1&!visitedj)/vi未访问 printf(visit vertex：c，G-vexsj)；/访问vi visitedj=TRUE； EnQueue(&Q，j)；/访问过的vi人队 /endwhile /BFSM/*DFS编码*/#define MAXVEX 100void dfs(adjlist g，int v,int n) /*从顶点v出发进行深度优先遍历*/ struct vexnode *stackMAXVEX, *p; int visitedMAXVEX,top=0; for(i=1;i0|p!=NULL) while(p!=NULL) if (visitedp-adjvex=1) p=p-next; else printf(“%d”,p-adjvex); visitedp-adjvex=1; top+; stacktop=p; p=gp-adjvex.link; if(top0) top-; /*退栈，回溯查找已被访问结点的未被访问过的邻接点 */ p=stacktop; p =p-next; 4图的遍历流程图4.1图的深度优先遍历流程图开始访问节点循环循环是否存在下一个节点访问下一个节点访问邻接点YESNO结束图4.1 图的深度优先遍历流程图4.2图的广度优先遍历流程图循环循环NOYES开始访问节点访问邻接点是否存在邻接点访问其它节点结束图4.2 图的广度优先遍历流程图 5系统运行运行环境与结果51运行环境在本课程设计中，系统开发平台为Windows Vista,程序设计语言为Visual C+6.0，程序的运行环境为Visual C+ 6.0。Visual C+一般分为三个版本:学习版、专业版和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual C+ 6.0为编程环境。Microsoft Visual C+ 6.0是Microsoft公司的Microsoft Visual Studio 6.0开发工具箱中的一个C+程序开发包。Visual C+包中除包括C+编译器外，还包括所有的库、例子和为创建Windows应用程序所需要的文档。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。 Visual C+从最早期的1.0版本，发展到最新的7.0版本，Visual C+已经有了很大的变化，在界面、功能、库支持方面都有许多的增强。最新的7.0版本在编译器、MFC类库、编辑器以及联机帮助系统等方面都比以前的版本做了较大改进。虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。Visual C+ 6.0是Microsoft公司推出的目前使用最广泛的基于Windows平台的可视化编程环境。Visual C+ 6.0是在以往版本不断更新的基础上形成的，由于其功能强大，灵活性好，完全课扩展以及具有强大的Internet支持，因而在各种C+语言开发工具中脱颖而出，成为目前最为流行的C+语言集成开发环境。Visual C+ 6.0秉承Visual C+以前版本的优异特性，为用户提供了一套良好的可视化开发环境：主要包括文本编辑器、资源编辑器、工程创建工具、Debugger调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运行、调试应用程序。52结构图及运行结果如下图5.2 结构图图5.3 运行结果6 课程设计总结转眼，为期两周的数据结构课程设计实习即将结束了。在这次实习中，自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：1.必须牢固掌握基础知识。由于C语言是大一所学知识，有所遗忘，且未掌握好这学期所学的数据结构这门课，所以在实习之初感到棘手。不知如何下手，但在后来的实习过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所熟悉。这时才逐渐有了思路。所以，这次实习之后，我告诫自己：今后一定要牢固掌握好专业基础知识。2.必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想这不仅是对于程序设计，做任何事都应如此。3.这次课程设计也让我充分认识到数据结构这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。总之，在这次实习中，自己的C语言以及数据结构知识得到提高，编程能力也得到了提高。最后，还得感谢我们的指导老师肖老师，如果没有他的精心指导，我也不会有如此多的收获。参考文献1 苏仕华 等编著.数据结构程序设计.北京：机械工业出版社.2005.52 潭浩强 编著。C语言程序设计（第三版）.北京：清华大学出版社.2005.73 严蔚敏，吴伟民 编著.数据结构（c 语言版）.北京：清华大学出版社.1997.44 郑莉，董渊 张瑞丰 编著.C+语言程序设计（第三版）.北京：清华大学出版社.2003.1附录：源程序代码/ 程序名称：COST1.CPP/ 程序功能：实现图的深度遍历和广度遍历/ 程序作者： / 最后修改日期：2010年7月13日#include#includestdio.h#includestdlib.husing namespace std;#define MaxVertexNum 50 /*定义最大顶点数*/typedef struct node /*边表结点*/ int adjvex; /*邻接点域*/ struct node *next; /*链域*/EdgeNode;typedef struct vnode /*顶点表结点*/ char vertex; /*顶点域*/ EdgeNode *firstedge; /*边表头指针*/VertexNode;typedef VertexNode AdjListMaxVertexNum; /*AdjList是邻接表类型*/typedef struct AdjList adjlist; /*邻接表*/ int n,e; /*图中当前顶点数和边数*/ ALGraph; /*图类型*/* 建立图的邻接表 */void CreatALGraph(ALGraph *G) int i,j,k; char a; EdgeNode *s; /*定义边表结点*/ printf(Input VertexNum(n) and EdgesNum(e): ); scanf(%d,%d,&G-n,&G-e); /*读入顶点数和边数*/ scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) /*建立边表*/ scanf(%c,&a); G-adjlisti.vertex=a; /*读入顶点信息*/ G-adjlisti.firstedge=NULL; /*边表置为空表*/ printf(Input edges,Creat Adjacency Listn); for(k=0;ke;k+) /*建立边表*/ scanf(%d%d,&i,&j); /*读入边（Vi，Vj）的顶点对序号*/ s=(EdgeNode *)malloc(sizeof(EdgeNode); /*/生成边表结点*/ s-adjvex=j; /*邻接点序号为j*/ s-next=G-adjlisti.firstedge; G-adjlisti.firstedge=s; /*将新结点*S插入顶点Vi的边表头部*/ s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; /*邻接点序号为i*/ s-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; /*将新结点*S插入顶点Vj的边表头部*/ /* 定义标志向量，为全局变量 */typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/* DFS：深度优先遍历的递归算法 */void DFSM(ALGraph *G,int i) /*以Vi为出发点对邻接链表表示的图G进行DFS搜索*/ EdgeNode *p; printf(%c ,G-adjlisti.vertex); /*访问顶点Vi*/ visitedi=TRUE; /*标记Vi已访问*/ p=G-adjlisti.firstedge; /*取Vi边表的头指针*/ while(p) /*依次搜索Vi的邻接点Vj，这里j=p-adjvex*/ if(! visitedp-adjvex) /*若Vj尚未被访问*/ DF