


下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
图的遍历概念1、 图的遍历和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。注意:以下假定遍历过程中访问顶点的操作是简单地输出顶点。2、 布尔向量visited[0..n-1]的设置图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后,又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点,必须记住每个已访问的顶点。为此,可设一布尔向量visited[0..n-1],其初值为假,一旦访问了顶点Vi之后,便将visited[i]置为真。深度优先遍历(Depth-FirstTraversal)图的深度优先遍历的递归定义假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点叽若可未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-FirstSearch)0相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。2、 深度优先搜索的过程设x是当前被访问顶点,在对x做过访问标记后,选择一条从x出发的未检测过的边(x,y)。若发现顶点y已访问过,则重新选择另一条Mx出发的未检测过的边,否则沿边(x,y)到达未曾访问过的y,对y访问并将其标记为已访问过;然后从y开始搜索,直到搜索完从y出发的所有路径,即访问完所有从y出发可达的顶点之后,才回溯到顶点x,并且再选择一条从x出发的未检测过的边。上述过程直至庞出发的所有边都已检测过为止。此时,若x不是源点,则回溯到在x之前被访问过的顶点;否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过,若图G是连通图,则遍历过程结束,否则继续选择一个尚未被访问的顶点作为新源点,进行新的搜索过程。3、深度优先遍历的递归算法(1)深度优先遍历算法typedefenum{FALSE,TRUE}Boolean;//FALSE为0,TRUE为1Booleanvisited[MaxVertexNum];〃访问标志向量是全局量voidDFSTraverse(ALGraph*G){〃深度优先遍历以邻接表表示的图G,而以邻接矩阵表示G时,算法完全与此相同inti;for(i=0;i<G->n;i++)visited[i]=FALSE;〃标志向量初始化for(i=0;i<G->n;i++)if(!visited[i])//vi未访问过DFS(G,i);〃以vi为源点开始DFS搜索}//DFSTraverse邻接表表示的深度优先搜索算法voidDFS(ALGraph*G,inti){〃以vi为出发点对邻接表表示的图G进行深度优先搜索EdgeNode*p;printf("visitvertex:%c”,G->adjlist[i].vertex);〃访问顶点vivisited[i]=TRUE;〃标记vi已访问p=G->adjlist[i].firstedge;〃取vi边表的头指针while(p){//依次搜索vi的邻接点vj,这里j=p->adjvexif(!visited[p->adjvex])//若vi尚未被访问DFS(G,p->adjvex);//则以Vj为出发点向纵深搜索p=p->next;〃找vi的下一邻接点}}//DFS邻接矩阵表示的深度优先搜索算法voidDFSM(MGraph*G,inti){〃以vi为出发点对邻接矩阵表示的图G进行DFS搜索,设邻接矩阵是0,l矩阵intj;printf("visitvertex:%c",G->vexs[i]);〃访问顶点vivisited[i]=TRUE;for(j=0;j<G->n;j++)//依次搜索vi的邻接点if(G->edges[i][j]==1&&!visited[j])DFSM(G,j)//(vi,vj)EE,且vj未访问过,故vj为新出发点}//DFSM注意:遍历操作不会修改图G的内容,故上述算法中可将G定义为ALGraph或MGraph类型的参数,而不一定要定义为ALGraph和MGraph的指针类型。但基于效率上的考虑,选择指针类型的参数为宜。4、深度优先遍历序列对图进行深度优先遍历时,按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列,或简称为DFS序列。一个图的DFS序列不一定惟一当从某顶点x出发搜索时,若x的邻接点有多个尚未访问过,则我们可任选一个访问之。源点和存储结构的内容均已确定的图的DFS序列惟一①邻接矩阵表示的图确定源点后,DFS序列惟一DFSM算法中,当从vi出发搜索时,是在邻接矩阵的第i行上从左至右选择下一个未曾访问过的邻接点作为新的出发点,若这样的邻接点多于一个,则选中的总是序号较小的那一个。【例】对连通图G7用邻接矩阵表示时,以v0为初始出发点的DFS遍历过程如下图(a)所示,具体算法的执行过程【参见动画演示】。DFS序列是v0,v1,v2,v5,v4,v6,v3,v7②只有给出了邻接表的内容及初始出发点,才能惟一确定其DFS序列邻接表作为给定图的存储结构时,其表示不惟一。因为邻接表上边表里的邻接点域的内容与建表时的输入次序相关。因此,只有给出了邻接表的内容及初始出发点,才能惟一确定其DFS序列。【例】连通图G7用邻接表表示时,以v0为初始出发点的DFS算法的执行过程和DFS序列【参见动画演示】(3)栈在深度优先遍历算法中的作用深度优先遍历过程中,后访问的顶点其邻接点被先访问,故在递归调用过程中使用栈(系统运行时刻栈)来保存已访问的顶点。5、算法分析对于具有n个顶点和e条边的无向图或有向图,遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。从DFSTraverse中调用DFS(或DFSM)及DFS(或DFSM)内部递归调用自己的总次数为n。当访问某顶点vi时,DFS(或DFSM)的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接矩阵
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 课题开题报告:隋唐时期中印乐器融合互鉴研究
- 第四单元第18课 东晋南朝时期江南地区的开发2023-2024学年七年级上册历史同步教学设计(部编版)
- 人教版七年级生物上册二次备课教学设计:第二单元第二章第一节细胞通过分裂产生新细胞
- 鼻窦炎的X射线影像
- 14 普罗米修斯 教学设计-2024-2025学年统编版语文四年级上册
- 如何制作儿童教育类的教学课件
- 广东省肇庆市高中数学 第二十四课 两角和的余弦公式教学设计 新人教A版必修4
- 2024年湖南邵阳工业职业技术学院招聘笔试真题
- 2024年河北沧州海发产业发展有限公司招聘笔试真题
- 大数据在物联网领域的应用与发展
- 无人机救援任务操作培训方案
- 独家模特签约正规合同范例
- DB51T 2860-2021“天府名品”认证通 用规范
- 慢病控制体重
- DB3714T 0002-2020 园林绿化种植土壤
- 广州市花都区2024年八年级下学期《数学》期中试题与参考答案
- 大班科学活动小实验
- 银行批评与自我批评发言稿
- 交通安全知识培训试题(带答案)试卷打印版
- 建筑工地农民工实名制管理制度
- 工商企业管理毕业论文范文(4篇)
评论
0/150
提交评论