图的深度优先搜索遍历算法分析及其应用.pdf
万方数据4 2青海师范大学学报(自然科学版)2 0 0 7 年#d e I i r 塘t l A L S E OB 0 0 k 皿“s i t e d M A x V E R n 一N u M ；t y p e d e fs m l c te(I 群札o d e i n t 删v e x；e d g e r I o d e*n 既t e d g e；l 幽e n o d e竹p e d e f 吼m c tv a 田0 c I e c h a rd a t a；2 2 构造算法H l 群m l e*6 n 心；v o d e，A d j h S t M A)【一砥一N U M ；t y p e d e fB u c t v e x n o d ev 硎c e 8；i n tv m，e d g e n m；A I m p h；根据上述结构，我们可以构造出建立图G 的邻接表的具体算法v o i dc m 自髀p h(A I G r a p h G)图的邻接表 i n ti，j，k；e(1 群础*8；耐n 耐”以编号为顺序输入顶点信息(每个顶点占两位)：”)；州i-0；i n；i+)辩a r 武”2 一，E 屿u 8 t i】d 如)；A d j l i 8 t i 矗墙t e d g e=n u s E；p 血烈啪入组成边的点对(如：边为(1，2)，则输入1 缸，、一)；研k=l；k a d j v=j；s 一 n 麟t e d g e=A d j l i s t L i J 丘玛t e d g e；A d j H s t【i 6 琚t e d 即=s；s=(e d 唧0 d e*)r n a l l o c(s i“e d 鲫0 d e)；8 一 喇v e x=i；8 一 I l。吐e d g e=A 由u s t j 6 舟t e d g e；A d j H B t j 矗璐t e d g e=8；根据图的结构建立其所对应的邻接表后，可以用下述算法打印出邻接表v o i d8 1 1 0 w(A L G m p l l G)i n ti；d 培e n o d e*s；B=A d j【j s t L i J 丘碍t e d g e；州i-O；i a d j v e x)；8=s 一 删硝铲；Ip 血甙“、矿)；I显然，在建立邻接表的过程中，对邻接点的访问是无次序的，所以同。一个图的邻接表表示不唯一如图2 所示是图G 以顶点编号为O，l，2，l3，4，5，6，7 的输入顺序建立的邻接表23 图的D F S 遍历345图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其它顶6点访问且仅被访问一次通常有两条遍历图的路径：深度优先搜索7(D 印l l lF i I s tS e a r c h)和广度优先搜索(B m d t lF i 璐tS 曲)它们对无向图和有向图均适用3 1 丐遍历的基本思想图2 图G 的邻接表假设初始状态是图中所有顶点未曾被访问，从图中某个顶点v i 出发，访问此顶点，然后依次从V i的未被访问的邻接点出发深度优先遍历图，直至图中所有和v i 有路径的顶点都被访问到为止；若此时 万方数据 万方数据青海师范大学学报(自然科学版)2 0 昕年6 蕊遍历序列结果讨论(1)只给定一个无向图，则以遍历序列不一定唯一从图的某顶点v i 出发进行搜索时，若v i 的邻接点有多个尚未访问，可任选一个访问(2)只有确定了图的邻接表的内容及起始顶点，d f B 遍历序列才能唯一因为邻接表里的邻接点域的内容与建表时的输人次序相关7 基于掘算法的应用(1)求无向图中连通分量的个数求解该问题只要在算法豳扛a 中加入一个计数器戚，每调用一次以后，使c n 加1，最后一t 的值就是无向图中连通分量的个数(2)求解无向图中通过给定顶点v i 的简单回路的算法【3 1从给定的顶点v i 出发进行深度优先搜索，搜索过程中每访问一个顶点，判别它是否为v i，若是，则说明已找到一条回路；否则继续搜索因此，用个顺序栈记录构成回路的顶点序列。把访问顶点的操作改为顶点的人栈，此时若从某一顶点出发搜索完再回溯，则做退栈操作另外再设置一个标志细咀d，其初值为F A I s E，当找到回路后改为T R【I E 综上所述，图的结构比较复杂，在编写图的D F S 算法和程序时，关键要掌握它的遍历思想，并且能使用一些编程技巧和经验对程序进行优化在完全理解D F s 算法的基础上，再去解决有关图的一些问题就显得容易了参考文献：n】严蔚敏，吴伟民数据结构 M】北京：清华大学出版社1 9 9 7：1 6 0-1 7 8 2】胡学钢数据结构算法设计指导 M】北京：清华大学出版杜1 9 盼：1 9 8 _ 2 1 6【3】于硗敏，唐丽用遍历方式求解圈中是否存在回路同题【J】齐齐啥尔大学学报2 瞄2：4 4 4 6A l l a l y s i s 锄dA p p n c a t i 伽F o rD e p l 一6 r s tS e a I I c l l 舢g o r i t l l I l lo fG 阳p h删帆1，胱雠2(1 D e p a】=h n e n to fC 锄”t e r，Q 岫a i d a H t 池咖袱弓i 哆。)(i n i l l g8 1 0 0，c h i I l a；2 D t j p 咖哪to f 日e c 附d cB I g i 肿既i I l ga n dh l f o I T 曲t i 叩S c i 唧e，Q i“g h a iN 出8 l i 如u m v 嗽崎，x i n i n g8 1 0 0 田。a l i n a)A l，s t r a c t：1 K 8 粥册a l y 掰c 蛳血U y t 堆D 印血一6 戚s e a l c hA l 护d t I 皿0 f t l l e G r 丑p h 吐I a t q 5 a I d e d 吐帕呐a-c 咖c yb s t 鼬8 幻r 8 胪g h I l c h l 陀山删曲p 删c I l l 盯既m。q d 鹧，“a I 鲫脚1 a l y 嘲山ew h o l ep I 珥乒锄m a l i z e d i nv c+A t l 出北，i tp 岫c 髂锨I 培印p 幽h 皓e d m t l l i 8 蜊t l l m 1 畸w o r d s：目r a p h；d e p 山一丘m t8 e 呲h；协n e r 曲_ l g；蜊t l l m 万方数据图的深度优先搜索遍历算法分析及其应用图的深度优先搜索遍历算法分析及其应用作者：刘萍，冯桂莲，LIU Ping，FENG Gui-lian作者单位：刘萍,LIU Ping(青海民族学院,计算机系,青海,西宁,810007)，冯桂莲,FENG Gui-lian(青海民族学院,电子工程与信息科学系,青海,西宁,810007)刊名：青海师范大学学报（自然科学版）英文刊名：JOURNAL OF QINGHAI NORMAL UNIVERSITY(NATURAL SCIENCE EDITION)年，卷(期)：2007，(3)引用次数：0次 参考文献(3条)参考文献(3条)1.严蔚敏.吴伟民 数据结构 19972.胡学钢 数据结构算法设计指导 19993.于晓敏.唐丽.于晓坤 用遍历方式求解图中是否存在回路问题期刊论文-齐齐哈尔大学学报（自然科学版）2004(2)相似文献(10条)相似文献(10条)1.期刊论文 魏国辉.杨春德.谭军.WEI Guo-hui.YANG Chun-de.TAN Jun DNA计算机中图的深度优先搜索遍历算法-计算机工程2008,34(15)提出DNA计算机中图数据结构的一种设计方法,给出具体的存储结构以及深度优先搜索遍历的算法.该算法实现了在DNA计算机下图元素的遍历.为证明其可行性,给出一个具体的算法实例,描述了DNA计算机上的运行机制.依据分子生物学的理论,证明算法是有效且可行的.2.会议论文 曹菡.卢俊岭.周影.黄春长 一种启发式路径查找深度优先搜索算法设计 2008 路径查找是人类的一项非常活动，其重要性得到人们的普遍认可。随着认知理论，环境心理学和空间信息科学的发展，作为多学科交叉的路径查找问题一直是人们所关注的研究内容。文章研究不熟悉校园环境中找路者的路径查找过程，在基于图的路径查找深度优先搜索算法基础上，利用方向关系和路牌信息，提出了一种启发式路径查找深度优先算法，较好地模拟了人们在不熟悉环境中的路径查找过程。本文以陕两师范大学新校区校园图为实验数据，验证了算法的可行性。本文工作表明构造路径查找形式化可计算模型的可能性。3.学位论文 郑丹 流体网络中单向回路问题的研究 2004 当路径的两个端点重合时就是回路,通路的两个端点重合时就是单向回路.流体网络中含有单向回路时,将会导致通路的矩阵算法以及有向图的搜索失败,计算通路数的公式、平衡图的绘制方法也不适用.该论文通过修改寻边策略,使深度优先搜索法适用于有单向回路的流体网络;通过流体网络拓扑关系等效变换的方法,将含有单向回路的流体网络变换成不含有单向回路的流体网络,即可利用平衡图的绘制方法绘制含有单向回路的流体网络的平衡图.该论文研究含有单向回路的流体网络的搜索和平衡图的绘制具有极其重要的实用价值.4.期刊论文 李海霞 图搜索策略与深度优先搜索的实现-考试周刊2009(1)本文通过实例分析,指出,将智能控制学科中的图搜索策略与数据结构中深度优先搜索算法相结合,能够得到计算机完成图搜索过程的方法.5.会议论文 虞成诚.钟声.胡绍华 基于深度优先搜索的一般图匹配算法 2008 对于一般图的匹配问题,Edmonds算法以Berge定理为基础,采用广度优先搜索增广路,图中可能存在花.遇到这种情况,要对它进行缩减花处理,再进行搜索.当找到增广路时,要将缩减图恢复,算法显得复杂.Gabow等算法使用先给目的顶点和边编号,并使用了不同数组和虚拟顶点,避免了处理花.算法的复杂性为O(n3),但增加了空间复杂性。本文提出的基于深度优先搜索算法,在搜索增广路时不会出现花的情况,算法相对简单;同时,算法时间效率为O(n*degree(n),degree(n)为顶点的平均度数.另外,当图的边动态增减时,使用该算法可以很快调整最大匹配,并且该算法空间复杂性在同一数量级也可以推广到广度优先搜索.6.期刊论文 刘峰.谭庆平.杨艳萍.LIU Feng.TAN Qing-ping.YANG Yan-ping 基于深度优先搜索的Web服务合成算法-计算机工程与科学2006,28(12)本文通过提取Web服务的语义信息,研究了语义Web服务合成问题.Web服务合成的关键是对候选Web服务的输入输出数据关系进行建模,以及有效地利用这些已有的数据依赖关系实现服务合成请求.通过构建Web服务的依赖图,提出了一种基于图论中深度优先搜索的Web服务合成算法,以获取满足特定要求的Web服务.7.学位论文 陆海晶 分布式数据库系统查询优化算法的研究 2007 首先介绍了分布式数据库系统的基本概念，然后简要描述了分布式查询的处理过程；重点描述了各种分布式数据库的查询处理及优化算法，如基于关系代数等价变换规则的优化算法、基于连接的优化算法、基于半连接的优化算法等。然后对基于Hash划分的分布式连接算法进行了详细讨论。特别是对CHAIN算法和Kruskal启发式算法的优缺点进行了较深入的分析和研究，以此为切入点，采用回溯法思想，对原有算法进行了改进。该优化算法对查询图进行深度优先搜索，产生各个边界点及相应的查询块。然后利用Kruskal启发式算法对特定的查询块进行优化。当一轮遍历结束后，算法将重新构造一个新的查询图，接着对该查询图以深度优先搜索，重复以上各步操作，直到查询图不能再分割为止。最后，对本算法进行了实验验证，实验结果表明使用该算法产生的关系连接序列花费的代价比传统的Kruskal启发式算法更小。8.期刊论文 李书琴.马耀光.许永功 图深度优先搜索技术在流域系统集成中的应用-西北农林科技大学学报(自然科学版)2003,31(5)介绍了数据结构中图的基本概念,并以渭河流域西部重点水源工程联合调度为例,说明了流域系统集成的基本思想和方法;应用图深度优先搜索技术,并采用数据库及可视化编程技术,进行了来水量关系分析与计算,为多水源工程联合调度和防洪决策支持系统自动化提供依据.9.学位论文 陈芹 基于逻辑综合工具的数字系统功能验证测试生成 199810.期刊论文 虞成诚.钟声.胡绍华.YU Cheng-cheng.ZHONG Sheng.HU Shao-hua 基于深度优先搜索的一般图匹配算法-计算机工程与科学2008,30(12)对于一般图的匹配问题,Edmonds算法以Berge定理为基础,采用广度优先搜索增广路,图中可能存在花.遇到这种情况,要对它进行缩减花处理,再进行搜索.当找到增广路时,要将缩减图恢复,算法显得复杂.Gabow等算法使用先给目的顶点和边编号,并使用了不同数组和虚拟顶点,避免了处理花.算法的复杂性为O(n3),但增加了空间复杂性.本文提出的基于深度优先搜索算法,在搜索增广路时不会出现花的情况,算法相对简单;同时,算法时间效率为O(n*degree(n),degree(n)为顶点的平均度数.另外,当图的边动态增减时,使用该算法可以很快调整最大匹配,并且该算法空间复杂性在同一数量级也可以推广到广度优先搜索.本文链接：http:/
