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

课程设计(论文)题 目 名 称 图的遍历 课 程 名 称 数据结构课程设计 学 生 姓 名 学 号 系 、专 业 信息工程系、电子科学技术 指 导 教 师 2012年 12 月 23 日 目 录1 前言22 需求分析22.1课程设计目的22.2课程设计任务22.3运行环境33 概要设计43.1总体设计流程43.2主函数流程图54 详细设计64.1实验的基本思想和基本原理64.2图的遍历65 算法描述95.1图的初始化95.2图的遍历106 结果与结论126.1源程序代码127课程设计总结17参考文献18致谢181 前言数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。2 需求分析2.1课程设计目的学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2.2课程设计任务1.问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2.逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法；3.详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架并画出模块之间的调用关系图；4.程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5.程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；2.3运行环境（1）WINDOWS 2000/2003/XP/7/Vista系统（2）Visual C+或TC集成开发环境193 概要设计3.1总体设计流程图用户登录录入图信息进入主菜单更改数据深度优先遍历广度优先遍历退出程序图3.1 总体设计流程图3.2主函数流程图BeginCreatueMGraph(G)ch1=ych1=y输入ch2CreatueMGraph(G)DFSTraverseM(G)BFSTraverseM(G)ch1=nbreakOverch2Y1N230图3.2 主函数流程图4 详细设计4.1实验的基本思想和基本原理和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。遍历常用两种方法：深度优先搜索遍历；广度优先搜索遍历 4.2图的遍历1图的深度优先搜索深度优先搜索是一种递归的过程，正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续下去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。图的深度优先遍历的递归定义 假设给定图4.1的初态是所有顶点均未曾访问过。在图中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。深度优先搜索的过程 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。算法思路 :(1)、首先访问一个顶点vi(初始点),将其标记为已访问过(因为图的每个顶点可能有多个前驱和后继，所以当一个顶点被访问以后，必须记录它已经被访问，以避免再次被访问，为此设置一个辅助数组visitedn, 它的每个元素的初值均为逻辑值假（false），即为常量0，表明尚未被访问，一旦访问了顶点vi，就将对应元素visitedi设置为逻辑值真，即为常量1，表明vi已被访问)。(2)、然后从vi的任一未被访问过的邻接点出发进行深度优先搜索遍历，当vi所有邻接点均被访问过，则退回到上一个顶点vk,从vk的另一个未被访问过的邻接点出发进行深度优先搜索遍历，直到退回到初始点并且没有未被访问过的邻接点为止。图4.1 (a)访问vo, 记录visited0=True, 从v0的一个未被访问过的邻接点v1出发遍历； (b)访问v1, visited1=True,从v1的一个未被访问过的邻接点v4出发遍历； (c)访问v4, visited4=True,从v4的一个未被访问过的邻接点v5出发遍历； (d)访问v5, visited5=True,由于v5的两个邻接点v1和v4都被访问过，退回上一邻接点v4，又v4的两个邻接点v1和v5都被访问过，再退回上一邻接点v1,从未被访问过邻接点V6出发遍历； (e)访问v6, visited6=True,从v6的一个未被访问过的邻接点v2出发遍历； (f)访问v2, visited2=True,v2所有邻接点都访问过，退回上一顶点v6,同理，v6退回v1,v1退回v0,再从v0未被访问过邻接点v3出发遍历；(g)访问v3, visited3=True，退回v0,因所有邻接点都访问过，再退回，结束。2图的广度优先搜索广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。广度优先搜索的基本思想首先访问图4.2中指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、 Vk，并均标记为已访问过，然后再按照Vj、Vk的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止在广度优先搜索中，若对顶点V1的访问先于顶点V2的访问，则对V1邻接顶点的访问也先于V2邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。设此队列由一个一维数组构成，数组名为Queue，队首指针和队尾指针分别为front和rear。假设数组足够大，不必考虑有溢出的可能性。广度优先搜索不是递归过程，不能用递归形式。图4.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所有未被访问过的邻接点(无)，结束。5 算法描述5.1图的初始化1定义图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; /*图类型*/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的边表头部*/ 5.2图的遍历1图的深度优先搜索算法#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; 时间复杂性一个有n个顶点、e条边的图，在深度优先搜索图的过程中，找邻接点所需时间为O(e)。对辅助数组初始化时间为O(n)。因此，当用邻接表作为图的存储结构时，深度优先搜索图的时间复杂性为O(e+n)。2图的广度优先搜索算法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 /BFSM6 结果与结论6.1源程序代码#includestdio.h#includestdlib.h#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) 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尚未被访问*/ DFSM(G,p-adjvex); /*则以Vj为出发点向纵深搜索*/ p=p-next; /*找Vi的下一个邻接点*/ void DFS(ALGraph *G) int i; for(i=0;in;i+) visitedi=FALSE; /*标志向量初始化*/ for(i=0;in;i+) if(!visitedi) /*Vi未访问过*/ DFSM(G,i); /*以Vi为源点开始DFS搜索*/* BFS：广度优先遍历 */void BFS(ALGraph *G,int k) /*以Vk为源点对用邻接链表表示的图G进行广度优先搜索*/ int i,f=0,r=0; EdgeNode *p; int cqMaxVertexNum; /*定义FIFO队列*/ for(i=0;in;i+) visitedi=FALSE; /*标志向量初始化*/ for(i=0;in;i+) cqi=-1; /*初始化标志向量*/ printf(%c ,G-adjlistk.vertex); /*访问源点Vk*/ visitedk=TRUE; cqr=k; /*Vk已访问，将其入队。注意，实际上是将其序号入队*/ while(cqf!=-1) / 队列非空则执行 i=cqf; f=f+1; /*Vi出队*/ p=G-adjlisti.firstedge; /*取Vi的边表头指针*/ while(p) /*依次搜索Vi的邻接点Vj（令p-adjvex=j）*/ if(!visitedp-a