图的广度深度优先遍历课程设计.doc

长沙理工大学数据结构课程设计报告图的广度深度优先遍历钱学帅学 院 计算机与通信工程 专 业 网络工程 班 级 网络07-1 学 号 04 学生姓名 钱学帅 指导教师 陈倩诒 课程成绩 完成日期 2009年3月12日、课程设计成绩评定学 院 计算机与通信工程 专 业 网络工程 班 级 网络01-1 学 号 200758080104 学生姓名 钱学帅 指导教师 陈倩诒 完成日期 2009.3.12 指导教师对学生在课程设计中的评价评分项目优良中及格不及格课程设计中的创造性成果学生掌握课程内容的程度课程设计完成情况课程设计动手能力文字表达学习态度规范要求课程设计论文的质量指导教师对课程设计的评定意见综合成绩 指导教师签字 2009年3月12日课程设计任务书计算机与通信工程学院 网络工程专业 课程名称数据结构课程设计时间20082009学年第2学期12周学生姓名钱学帅指导老师陈倩诒题 目图的广度深度优先遍历主要内容：在图的邻接表存储结构下（1） 图的广度优先遍历（2） 图的深度优先遍历要求：（1）通过实际项目的分析、设计、编码、测试等工作，掌握用C语言来开发和维护软件。（2）按要求编写课程设计报告书，能正确编写分析、设计、编码、测试等技术文档和用户使用手册。应当提交的文件：（1）课程设计学年论文。（2）课程设计附件（主要是源程序）。图的广度深度优先遍历学生姓名：钱学帅 指导老师：陈倩诒 摘 要 我们希望从图中某一顶点出发访遍图中其余各顶点，且使每一顶点仅被访问一次，这个过程就叫图的遍历。而图的深度优先遍历类似与树的先根遍历，是树的先根遍历的推广，图的广度优先遍历是类似于树的按层次遍历的过程。图的遍历过程实质上就是通过边或者弧找邻接点的过程。在这，我们主要就是介绍遍历图的两种基本方法：深度优先搜索和广度优先搜索。这两种方法无论是有向图还是有向图都适用。广度优先搜索遍历图和深度优先搜索遍历图的时间复杂度相同，两者不同之处仅仅在于对顶点访问的顺序不同。 关键词 图的遍历；广度优先遍历；深度优先遍历； 目录1 引言12设计思路与方案 2 2.1设计思路2 2.2设计方案23 详细实现4 31队列的定义及相关操作432图的邻接表存储结构的定义及无向图的建立 5 33图的深度优先遍历算法6 34图的广度优先遍历非递归算法74 运行环境与结果8 4.1运行环境84.2 运行结果95结束语12参考文献13附录14长沙理工大学 数据结构课程设计 第 18 页 共 18 页1 引 言 图的遍历算法是求解图的连通性问题，拓扑排序和求关键路径等算法的基础。然而，图的遍历要比树的遍历复杂的多。因为图的任何一顶点都有可能和其余的顶点相邻接。所以在访问了某个顶点之后，可能沿着某条路径搜索之后，又回到该点是行。为了避免同一顶点被访问多次，在图的遍历过程中，必须先记下每个已访问的顶点。在次介绍两种对有向图和无向图都适用的遍历图的路径：深度优先搜索和广度优先搜索。在此次设计中，用到的最多的队列，图的深度优先遍历类似于树的前序遍历。采用的遍历方法的特点是尽可能先对纵深方向进行搜索。广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，鼓称其为广度优先搜索，相应的遍历称为广度优先遍历。通过课程设计，我们会认识自身存在的很多问题，也有利于提高我们的动手能力，也把我们所学的东西和实践很好的结合起来，在这次设计中，再次体会了队列，深度优先搜索，广度优先搜索，等数据结构中的基本算法及其原理。2 设计思路与方案2.1设计思路在遍历图时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实际上就是对每个顶点查找其临界点的过程。其耗费的时间则取决与所采用的存储结构。当用二维数组表示邻接作图的存储结构时，查找每个顶点的临界点所需的时间为0（n2），其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需要的时间为0（e），其中e 为无向图中边的数或者有向图中弧的数。遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先遍历相同，两者不同之处仅仅在于对顶点的访问的顺序不同。2.2设计方案 （1）图的深度优先遍历：假设初始状态是图中所有的饿点未曾被访问，则深度优先搜索可从图中某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的的顶点起作起始点，重复上述过程，直至图中所有顶点都被访问到为止。（2）图的广度优先遍历：假如从图中某顶点V出发，在访问了V之后依次访问V的各个未曾被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问为止。3 详细实现31队列的定义及相关操作为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问X和Y时，这两个顶点相继入队。此后，当X和Y相继出队时，分别从X和Y出发搜索其邻接点X1，X2，XS和Y1Y2YT，对其中未访问者进行访问并将其入队，这种方法是将每个已访问的顶点入队，故保证了每个顶点至多只有一次入队。因此用队列。typedef struct/队列结点的定义3int *base;int front;int rear;SqQueue;int InitQueue(SqQueue *Q)/构造空队列 Q-base=(int *)malloc(MAXQSIZE*sizeof(int); if(!Q-base) exit(OVERFLOW); Q-front=Q-rear=0; return OK;int QueueEmpty(SqQueue Q)/判队空 return Q.rear=Q.front;int QueueFull(SqQueue Q)/判队满 return (Q.rear+1)%MAXQSIZE=Q.front;int EnQueue(SqQueue Q,int x)/入队 if(QueueFull(Q) return ERROR; Q.baseQ.rear = x; Q.rear=(Q.rear+1)%MAXQSIZE; return OK;int DeQueue(SqQueue Q,int x)/出队 if(QueueEmpty(Q) return ERROR; x=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE;return OK; 在图的广度优先遍历非递归程序中会用到队列操作。32图的邻接表存储结构的定义及无向图的建立typedef struct ArcNodeint adjvex; /该弧所指向的顶点的的位置 struct ArcNode *nextarc;/指向下一条弧的指针int *info;2ArcNode;typedef struct VNode int data; /顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef struct ALGraph AdjList vertices; /一维数组存放 int vexnum,arcnum; /顶点数和弧的条数 int kind;ALGraph;int locatevex(ALGraph *G,int v) /返回顶点v在图中的位置i int i;for(i=0;ivexnum;i+)if(v=G-verticesi.data)break;return i;status CreateAL2(ALGraph *G) /建立无向图int n,e,i,j,k,vt,vh,m;ArcNode *p,*q;printf(请先后输入顶点数和边数：);3scanf(%d%d,&G-vexnum,&G-arcnum); /输入顶点数和弧的/条数 n=G-vexnum;e=G-arcnum;G-kind=2;printf(请输入顶点值：); for(m=0;mverticesm.data); G-verticesm.firstarc=NULL;printf(请输入边，即一条边的两顶点：); for(k=1;kadjvex=j;p-nextarc=G-verticesi.firstarc;G-verticesi.firstarc=p; q=(ArcNode *)malloc(sizeof(ArcNode); /由于边可视为对称两/条弧，故再申请一个表头结点存放序号i, 并将其插入到vj的单链表/中 4 q-adjvex=i;q-nextarc=G-verticesj.firstarc;G-verticesj.firstarc=q; return OK; 33图的深度优先遍历算法从图中的某个顶点vi出发，先访问该顶点vi，然后依次从vi的未被访问过的邻接点出发执行深度优先遍历算法；直至图中所有和vi有路径相通的顶点都被访问到为止。 若此时图中还有未被访问到的顶点（即非连通图的情形），则再选图中一个未被访问过的顶点vj作为起点重复上述过程，直至图中所有顶点均被访问过为止。int FirstAdjVex(ALGraph G,int i) /求i号顶点的第一个邻接点的序号int j;ArcNode *p=G.verticesi.firstarc;if(p)j=p-adjvex; else j=-1; return j;int NextAdjVex(ALGraph G,int i,int j) /求i号顶点的处于序号为j的/邻接点的后面的“再下一个邻接点”的序号ArcNode *p=G.verticesi.firstarc; while(p)&(p-adjvex!=j)p=p-nextarc;p=p-nextarc;if(p)return p-adjvex; else return -1;int visited100;/记录结点是否被访问过int DFS(ALGraph G,int i)int j; visitedi=TRUE; printf(%d ,G.verticesi.data); /访问（即打印）i号结点 for(j=FirstAdjVex(G,i);j!=-1;j=NextAdjVex(G,i,j) if(!visitedj)DFS(G,j); return OK; 深度优先遍历主函/DFSvoid DFStraverse(ALGraph G)/ 图的数 int i; for(i=0;iG.vexnum;+i)visitedi=FALSE; for(i=0;iG.vexnum;+i) if(!visitedi) DFS(G,i);/DFStraverse34图的广度优先遍历非递归算法从图中的某个顶点vi出发，先访问该顶点vi，然后依次访问vi的各个未曾访问过的邻接点，然后再依次访问这些邻接点的邻接点；重复上述过程，直至图中所有和vi有路径相通的顶点都被访问到为止。若此时图中还有未被访问到的顶点（即非连通图的情形），则再选图中一个未被访问过的顶点vj作为起点重复上述过程，直至图中所有顶点均被访问过为止。void BFStraverse(ALGraph G) int v,w;SqQueue Q;InitQueue(&Q); /初始化队列 for(v=0;vG.vexnum;+v)visitedv=FALSE;for(v=0;vG.vexnum;+v) /从序号为0的顶点开始 if(!visitedv) visitedv=TRUE;printf(%d ,G.verticesv.data); EnQueue(Q,v); /刚被访问的结点的序号进队 while(!QueueEmpty(Q) /找出刚出队的顶点（序号）的全/部邻接点（序号），若该结点还没打印（即没访问）过则打印后进队 DeQueue(Q,v); for(w=FirstAdjVex(G,v);w!=-1;w=NextAdjVex(G,v,w) if(!visitedw) visitedw=TRUE;printf(%d ,G.verticesw.data);EnQueue(Q,w); /while /if/BFStraverse4 运行环境与结果4.1运行环境在本课程设计中，系统开发平台为WindowsXP,程序设计语言为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调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运行、调试应用程序。4.2运行结果.1建立一个图，如图4-1建立一个顶点数为11，弧数为12的图，用该图来举例说明该程序的可行性。 图4-1 2打开VC+6.0中文版，如图4-2所示。 图4-2 VC+6.0的工作界面3，检测以后没错误，运行得图4-3 图4-3 程序开始运行程序提示“请先输入顶点和边数”，顶点数与边数之间用空格各开，按Enter输入.4输入图4-4所示的顶点和弧 图4-4输入顶点和弧分别为11 12程序提示“请输入顶点值”，每输入一个值，按Enter输入，如下图。5各结点的输入 图4-5输入结点图4-6输入边得结果输入边后按Enter，显示深度与广度遍历序列5 结束语这次的课程设计的内容是以邻接矩阵的方式确定一个图，完成：建立并显示出它的代码我已经找到邻接链表；给出某一确定顶点到所有其它顶点的最短路径；，这对我来说是个很具有挑战性的任务，虽然做的不是很好，但通过两个星期的设计也从中学到了不少东西，更深刻的理解了课本中的内容。数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。同时再次深刻理解了C语言的实用，文件的概念和相关操作，单链表和顺序表在时间性能及空间性能方面的优缺点。根据实际问题的需要，对个方面的优缺点加以综合平衡，从中选择比较适宜的实现方法。在本次课程设计中，我明白了理论与实际相结合的重要性，并提高了自己组织数据及编写程序的能力，培养了基本的，良好的程序设计技能。提高综合运用所学知识的能力。在这次课程设计中曾遇到了不少问题，就单凭我一个人的能力很难准时有效的完成这次的课程设计，因此在网上找了很资料，而且也认真的请教了同学。同学们也很热心，非常感谢他们，也因此加强了和同学们的感情。再次感谢我的指导老师，陈倩诒老师。陈老师对工作认真负责，耐心辅导，知识丰富。在这次课程设计中给了我很大的帮助。她严谨的治学精神和深厚的理论水平都使我获益非浅。参考文献1王红梅，胡明，王涛. 数据结构(C+版) . 北京：清华大学出版社，20072 王红梅，胡明，王涛. 数据结构(C+版) 学习辅导与实验指导. 北京：清华大学出版, 20073严蔚敏 , 吴伟民 数据结构(C语言版). 清华大学出版社 20084郑阿奇，丁有和. Visual C+教程.北京：机械工业出版社，2006附录：源程序代码 define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define NULL 0typedef int status;#include#include#include#define MAX_VERTEX_NUM 20#define MAXQSIZE 100typedef structint *base;int front;int rear;SqQueue;int InitQueue(SqQueue *Q)/构造空队列 Q-base=(int *)malloc(MAXQSIZE*sizeof(int); if(!Q-base) exit(OVERFLOW); Q-front=Q-rear=0; return OK;int QueueEmpty(SqQueue Q)/判队空 return Q.rear=Q.front;int QueueFull(SqQueue Q)/判队满 return (Q.rear+1)%MAXQSIZE=Q.front;int EnQueue(SqQueue Q,int x)/入队 if(QueueFull(Q) return ERROR; Q.baseQ.rear = x; Q.rear=(Q.rear+1)%MAXQSIZE; return OK;int DeQueue(SqQueue Q,int x)/出队 if(QueueEmpty(Q) return ERROR; x=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE;return OK; typedef struct ArcNodeint adjvex; struct ArcNode *nextarc;int *info;ArcNode;typedef struct VNode int data; ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct ALGraph AdjList vertices; int vexnum,arcnum; int kind;ALGraph;int locatevex(ALGraph *G,int v)int i;for(i=0;ivexnum;i+)if(v=G-verticesi.data)break;return i;status CreateAL2(ALGraph *G)int n,e,i,j,k,vt,vh,m;ArcNode *p,*q;printf(请先后输入顶点数和边数：); scanf(%d%d,&G-vexnum,&G-arcnum); n=G-vexnum;e=G-arcnum;G-kind=2;printf(请输入顶点值：); for(m=0;mverticesm.data); G-verticesm.firstarc=NULL;printf(请输入边，即一条边的两顶点：); for(k=1;kadjvex=j;p-nextarc=G-verticesi.firstarc;G-verticesi.firstarc=p; q=(ArcNode *)malloc(sizeof(ArcNode); q-adjvex=i;q-nextarc=G-verticesj.firstarc;G-verticesj.firstarc=q; return OK;int FirstAdjVex(ALGraph G,int i)int j;ArcNode *p=G.verticesi.firstarc;if(p)j=p-a