图的深度优先搜索遍历算法分析及其应用

维普资讯 http://www.cqvip.com ２００７正　青海师范大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｑｉｎｇｈａｉ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　２Ｏ０７　Ｎｏ．３　第３期　图的深度优先搜索遍历算法分析及其应用　５ｒ４　萍　，冯桂莲２　（１．青海民族学院计算机系，青海西宁８１０００７；２．青海民族学院电子工程与信息科学系，青海西宁８１０００７）　摘要：本文通过具体的示例，详细分析以邻接表为存储结构进行图的深度优先搜索遍历的算法和在ｖｃ＋＋环境中实现的完　整程序，最后介绍了基于该算法一些应用．　关键词：图；深度优先搜索；遍历；算法　中图分类号：ＴＰ３１１．１２　文献标识码：Ａ　文章编号：１００１—７５４２｛２ＯＹ／｝０３—００４１—０４　图（ｃｒａｐｈ）是一种较线性表和树更为复杂的数据结构．图形结构中，结点之间的关系可以是任意的，　图中任意两个数据元素之间都可能相关．因此，在研究有关图的问题时，要考虑图中每个顶点的信息，访　问图中的各顶点，而访问图中各顶点的操作过程就是图的遍历．图的遍历算法是求解图的连通性问题、　拓扑排序和求关键路径等算法的基础．　１图的二元组定义　图Ｃ由集合Ｖ和Ｅ组成，记为：Ｇ＝（Ｖ，Ｅ）．其中：Ｖ是顶点的集合，Ｅ是Ｖ中顶点偶对的有穷集．通　常，将图ｃ的顶点集和边集记为Ｖ（Ｇ）和Ｅ（Ｇ）．Ｅ（ｃ）可以是空集，若Ｅ（ｃ）为空，则图Ｇ只有顶点而没有　边．　２图的存储结构　图的存储结构有邻接表、十字链表和多重邻接表等，本文主要介绍邻接表的存储结构．邻接表（Ａｄ．　ｊａｃｅｎｃｙ　Ｌｉｓｔ）是图的一种链式存储结构．邻接表包含了一个顶点顺序表和每个顶点对应的单链表．顶点顺　序表中的顶点与图中的顶点一一对应，每个顶点的单链表中包含了邻接点域，链域和数据域．它是一个　动态结构，相当于是建立多个线性链表的操作ｕ　Ｊ．　为了便于理解，本文以无向图Ｇ作为具体示例（如图１所示），给　出以邻接表进行存储的图的数据结构．　现将图Ｇ的各顶点进行编号，其对应关系如表１所示：　表１顶点与编号的对应关系　２．１邻接表的数据结构定义　图１无向图Ｇ　将图ｃ采用邻接表存储，其结构定义如下：　＃ｉｎｃｌｕｄｅ＜ｓｔｄｉｏ．ｈ＞　＃ｉｎｃｌｕｄｅ　ｍａｌｌｏｃ．ｈ“　＃ｄｅｆｉｎｅ　ＭＡＸ　ＶＥ　ｒＥＸ　ＮＵＭ　３０　＃ｄｅｆｉｎｅ　ｎ　８　＃ｄｅｆｉｎｅ　ｅ　９　＃ｄｅｆｉｎｅ　ＴＲＵＥ　１　收稿日期：２ＯＯ７—０３—１６　作者简介：刘萍（１９６８一），女（汉族），青海同仁人，青海民族学院副教授　维普资讯 http://www.cqvip.com

４２　＃ｄｅｆｉｎｅ－　Ｅ　０　青海师范大学学报（自然科学版）　ｅｄｇｅｎｅｄｅ＊ｆｉｒｓｔｅｄｇｅ；　２００７年　Ｂｏｏｌｅａｍ　ｖｉｓｉｔｅｄ［ＭＡＸ—ＶＥＲＴＥＸ—ＮＵＭＪ；　ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　ｅｄｇｅｎｅｄｅ　｝ｖｅｘ．ｎｄｅ，ｅＡｄｊＨｓｔ［ＭＡＸ—ＶＥＲＴＥＸＮＵＭ］；　—ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　｛ｈａｔ　ａｄｊｖｅｘ；ｅｄｇｅｎｅｄｅ＊ｎｅｘｔｅｄｇｅ；｝ｅｄｇｅｎｅｄｅ；　ｔｙｐｅｄｅｆ　ｓｔｒｕｃｔ　ｖｅｘｎｅｄｅ　｛ｖｅｘｎｏｄｅ　ｖｅｒｔｉｃｅｓ；　ｉｎｔ　ｖｅｘｎｕｍ，ｅｄｇｅｎｕｍ；　｛ｃｈａｒ　ｄａｔａ；　２．２构造算法　｝ＡＩ￣ｍｐｈ；　根据上述结构，我们可以构造出建立图Ｇ的邻接表的具体算法．　ｖｏｉｄ　ｃｒｅａｔｇｒａｐｈ（ＡＬＧｒａｐｈ＆Ｇ）　｛　ｉ，ｊ，ｋ；ｅｄｇｅｎｅｄｅ＊ｓ；　／／图的邻接表　ｐｒｉｎｆｆ（”以编号为顺序输入顶点信息（每个顶点占两位）：”）；　ｆ０ｌｒ（ｉ＝Ｏ；ｉ＜ｎ；ｉ＋＋）　｛ｓｃａＩｌｆ（”％２ｄ，，，＆ａｄｊｌｉｓｔ［ｉ］．ａｔｄａ）；　Ａｄｊｌｉｓｔ［ｉ］．ｉｆｒｓｔｅｄｇｅ＝　Ｅ；｝　ｐｒｍ￣（，输入组成边的点对（如：边为（１，２），则输入１　２／＼Ｉｌ，，）；　ｆｏｒ（ｋ＝ｌ；ｋ＜＝ｅ；ｋ＋＋）　｛ｐｒｉｎｆｆ（　，第％ｄ条边的点对：”，ｋ）；ｓｃａｒｆ（”％ｄ％ｄ，，，蕊，　）；　Ｓ＝（ｅｄｇｅｎｅｄｅ＊）ｍａｉｌｏｃ（ｓｉｚｅｏｆ（ｅｄｇｅｎｅｄｅ））；Ｓ一＞ａｄｊｖｅｘ＝ｊ；　ｓ一＞ｎｅｘｔｅｄｇｅ＝Ａｄｊｌｉｓｔ［ｉ］．ｉｆｒｓｔｅｄｇｅ；Ａｄｊｌｉｓｔ［ｉ］．ｉｆｒｓｔｅｄｇｅ＝ｓ；　ｓ＝（ｅｄｇｅｎｅｄｅ＊）ｍａｌｌｏｃ（ｓｉｚｅｏｆ（ｅｄｇｅｎｅｄｅ））；Ｓ一＞ａｄｊｖｅｘ＝ｉ；　ｓ一＞ｎｅｘｔｅｄｇｅ＝Ａｄｊｌｉｓｔ［ｊ］．ｉｆｒｓｔｅｄｇｅ；Ａｄｊｌｉｓｔ［ｊ］．ｉｆｒｓｔｅｄｇｅ＝ｓ；｝｝　根据图的结构建立其所对应的邻接表后，可以用下述算法打印出邻接表．　ｖｏｉｄ　ｓｈｏｗ（ＡＬＧｍｐｈ＆Ｇ）　｛ｉｎｔ　ｉ；ｅｄｇｅｎｅｄｅ＊ｓ；　ｏｒ（ｉ＝Ｏ；ｉ＜ｎ；ｉ＋＋）ｆ　｛ｓ＝ＡｄｊＬｉｓｔ［ｉ］．ｆｉｓｒｔｅｄｇｅ；　｛ｐｒｉｎｆｆ（”％９ｄ：一”，ＡｄｊＬｉｓｔ［ｉ］．ｄａｔａ）；　ｉｆ（Ａｄｊｌｉｓｔ［ｉ］．ｉｆｒｓｔｅｄｇｅ！：ＦＡＬＳＥ）　ｗｈｉｌｅ（ｓ！＝ＦＡＬＳＥ）　｛ｐｒｎｔｉｆ（”％５　”，Ｓ一＞ａｄｊｖｅｘ）；　ｓ＝ｓ一＞ｎｅｘｔｅｄｇｅ；｝｝　ｐｒｎｉｔｆ（　＼Ｉｌ，，）；｝｝　一显然，在建立邻接表的过程中，对邻接点的访问是无次序的，所以同　Ｖｌ　个图的邻接表表示不唯一．如图２所示是图Ｇ以顶点编号为０，１，２，１　Ｖ２　Ｖ３　２　Ｖ４　３　４　Ｖ５　３，４，５，６，７的输入顺序建立的邻接表．　３图的ＤＦＳ遍历　５　Ｖ６　Ｖ７　图的遍历是从图中某个顶点出发，沿着某条搜索路径对图中其它顶６　Ｖ８　点访问且仅被访问一次．通常有两条遍历图的路径：深度优先搜索７　（Ｄｅｐｔｈ　Ｆｉｒｓｔ　Ｓｅａｒｃｈ）和广度优先搜索（Ｂｒｅａｄｔｈ　Ｆｉｓｒｔ　Ｓｅａｒｃｈ）．它们对无向图　和有向图均适用．　３．１　ＤＦＳ遍历的基本思想　图２图Ｇ的邻接表　假设初始状态是图中所有顶点未曾被访问，从图中某个顶点Ｖｉ出发，访问此顶点，然后依次从Ｖｉ　的未被访问的邻接点出发深度优先遍历图，直至图中所有和Ｖｉ有路径的顶点都被访问到为止；若此时　维普资讯 http://www.cqvip.com 第３期　刘萍，冯桂莲：图的深度优先搜索遍历算法分析及其应用　４３　图中尚有顶点未被访问，则另选图中未曾访问的顶点为起始点，重复上述过程，直至图中所有顶点都被　访问为止　２．　３．２　ＤＦＳ遍历的具体步骤　（１）先将图中所有顶点标记为“未被访问”标志；　（２）输出起始顶点，同时置起始顶点“已访问”标记；　（３）将起始顶点进栈；　（４）当栈不为空时重复执行以下步骤：　①取当前栈顶顶点；　②若栈顶顶点存在未被访问的邻接顶点，则选择一个顶点并输出；　③置该顶点为“已访问”标志，将该顶点进栈；否则，当前顶点退栈．　３．３　ＤＦＳ遍历的算法设计　结合示例，我们可以设一个辅助数组ｖｉｓｉｔｅｄ［ｎ］，将其初始值均置为“０”，一旦访问了顶点ｖｉ，便将　ｉｖｓｉｔｄ［ｉｅ］置为“１”，其具体算法如下：　ｖｏｉｄｄｆｓｔｒａｖｅｒｓｅ（ＡＬＧｍｐｈ＆Ｇ）　，ｅｄｇｅｎｅｄｅ＊・ｐ；　｛ｉｎｔ　ｉ；ｆｏｒ（ｉ＝Ｏ；ｉ＜ｎ；ｉ＋＋）ｖｉｓｉｔｅｄ［ｉ］＝ＦＡＬＳＥ；　ｆｏｒ（ｉ＝０；ｉ＜ｎ；ｉ＋＋）ｐｒｉｎｔｆ（”％ｄ一＞”，ＡｄｊＬｉｓｔＥｉ］．ｄａｔａ）；　ｉｖｓｉｔｅｄＥｉ］＝ＴＲＵＥ；　Ｐ＝ＡｄｊＬｉｓｔ［ｉ］．ｆｉｒｓｔｅｄｇｅ；　ｉｆ（！ｖｉｓｉｔｅｄ［ｉ］）　ｗｈｉｌｅ（ｐ！：ＦＡＬＳＥ）　ｄｆｓ（Ｇ，ｉ）；｝　ｖｏｉｄ　ｄｆｓ（ＡＬＧｒａｐｈ＆Ｇ，ｉｎｔ　ｉ）｛ｓｔａｔｉｃ　ｉｎｔ　ｉｖｓｉｔｄｌＭＡＸ—ＶＥＲＴＥＸ—ＮＵＭ］；ｅ｛ｉｆ（！ｖｉｓｉｔｄ［ｅｐ一＞ａｄｊｖｅｘ］）　ｄｆｓ（Ｇ，Ｐ一＞ａｄｊｖｅｘ）；　Ｐ＝Ｐ一＞ｎｅｘｔｅｄｇｅ；｝｝　从上面算法看出，进行图的遍历时，对图中的每个顶点至多调用一次　，因此，图的遍历过程实际　上是对每个顶点查找其邻接点的过程．此外，由于图的邻接表是不唯一的，所以由不同的邻接表得到的　图的遍历结果也是不相同的．　４主程序　在给出了数据结构类型和具体操作的算法之　后，可以编辑出以下主程序：　ｖｏｉｄ　ｍａｉｎ（）　｛ｉｎｔ　ｘ；ＡＬＧｒａｐｈ　Ｇ；ｃｒｅａｔｇｒａｐｈ（Ｇ）；　ｐ血ｔｆ（　输出如下邻接表：＼ｎ”）；ｓｈｏｗ（Ｇ）；　ｐｒｉｎｔｆ（　＼ｎ输入访问出发点的顶点编号：”）；　ｓ￣ａｎｆ（”％ｄ，，，　）；　ｐｒｉｎｔｆ（”该图的深度优先搜索遍历序列为：＼ｎ＼　ｔ，，）．ｄｆｓ（Ｇ，ｘ）；　ｐｒｉｎｆｆ（”＼ｂ＼ｂ，，）；｝　５运行结果　该程序已经在Ｖｉｓｕａｌ　Ｃ＋＋环境中调试通过，运　行时输入的具体数据和相应结果如图３所示：　图３程序运行结果　维普资讯 http://www.cqvip.com 青海师范大学学报（自然科学版）　２Ｏ０７年　６　ｄｆｓ遍历序列结果讨论　（１）只给定一个无向图，则ｄｆｓ遍历序列不一定唯一．从图的某顶点ｖｉ出发进行搜索时，若ｖｉ的邻　接点有多个尚未访问，可任选一个访问．　（２）只有确定了图的邻接表的内容及起始顶点，　遍历序列才能唯一．因为邻接表里的邻接点域的　内容与建表时的输人次序相关．　７基于ｄｆｓ算法的应用　（１）求无向图中连通分量的个数　求解该问题只要在算法ｄｆｓｔｒａｖｅｒｓｅ中加人一个计数器ｃｏｕｎｔ，每调用一次　后，使ｃｏｕｎｔ加１，最后　ｃｏｕｎｔ的值就是无向图中连通分量的个数．　（２）求解无向图中通过给定顶点Ｖｉ的简单回路的算法［３】　从给定的顶点Ｖｉ出发进行深度优先搜索，搜索过程中每访问一个顶点，判别它是否为ｖｉ，若是，则　说明已找到一条回路；杏则继续搜索．因此，用一个顺序栈记录构成回路的顶点序列，把访问顶点的操作　改为顶点的人栈，此时若从某一顶点出发搜索完再回溯，则做退栈操作．另外再设置一个标志ｆｏｕｎｄ，其　初值为ＦＡＬＳＥ，当找到回路后改为ＴＲＵＥ．　综上所述，图的结构比较复杂，在编写图的ＤＦＳ算法和程序时，关键要掌握它的遍历思想，并且能　使用一些编程技巧和经验对程序进行优化．在完全理解ＤＦＳ算法的基础上，再去解决有关图的一些问　题就显得容易了．　参考文献：　［１】严蔚敏，吴伟民．数据结构［Ｍ】．北京：清华大学出版社．１９９７：１６０－１７８．　［２】胡学钢．数据结构算法设计指导［Ｍ】．北京：清华大学出版社．１９９９：１９８－２１６．　［３】于晓敏，唐丽．用遍历方式求解图中是否存在回路问题［Ｊ］．齐齐哈尔大学学报，２ＯＯ４，２：￣４６．　Ａｎａｌｙｓｉｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎ　Ｆｏｒ　Ｄｅｐｔｈ—ｆｉｒｓｔ　Ｓｅａｒｃｈ　Ａｌｇｏｒｉｔｈｍ　Ｏｆ　Ｇｒａｐｈ　ＬＩＵ胁　，ＦＥＮＧ　Ｇｕｉ－ｌｉａｎ　（１．Ｄｅｐａｒｔｍｅｎｔ　ＯｆＣｏｍｐｕｔｅｒ，Ｑｉｎｇｈａｉ　Ｎａｔｉｏｎａｌｉｔｉｅｓ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉｎｉｎｇ　８１０００７，Ｃｈｉｎａ；　２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ。Ｑｉｎｇｈａｉ　Ｎａｔｉｏｎａｌｉｉｔｅｓ　Ｕｎｉｖｅｒｓｉｔｙ，ｙａｎｉ￣８１０００７，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ａｎａｌｙｚｅｓ　ｃａｒｅｆｕｌｌｙ　ｔｈｅ　Ｄｅｐｔｈ—ｆｉｒｓｔ　Ｓｅａｒｃｈ　Ａｌｇｏｒｉｔｈｍ　ｏｆｔｈｅ　Ｇｒａｐｈ　ｔｈａｔ　ｒｅｇａｒｄｅｄ　ｔｈｅ　ａｄｊａ—　ｅｅｎｅｙ　ｌｉｓｔ　ａｓ　ｓｔｏｒａｇｅ　ｓｔｒｕｃ￣ｒｅ　ｔｈｒｏｕｇｈ　ｐａｒｔｉｃｕｌａｒ　ｅｘａｍｐｌｅｓ，ａｎｄ　ａｌｓｏ　ａｎａｌｙｚｅｓ　ｔｈｅ　ｗｈｏｌｅ　ｐｒｏｇｒａｍ　ｒｅａｌｉｚｅｄ　ｉｎ　ｖｅ＋＋．　Ａｔ　ｌａｓｔ．ｉｔ　ｐｒｏｄｕｃｅｓ　８咖ｅ　ａｐｐｌｉｃａｔｉｏｎ　ｂａｓｅｄ　Ｏｉｌ　ｔｈｉｓ　ａｓｏｒｉｔｈｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｇｒａｐｈ；ｄｅｐｔｈ——ｆｉｒｓｔ　ｓｅａｒｃｈ；ｔｒａｖｅｒｓｉｎｇ；ａｌｇｏｒｉｔｈｍ