基于栈的非递归深度优先遍历算法设计与实现

时间：2013-07-04 18:15:44 来源：论文投稿

摘要：深度优先遍历是图的一种重要遍历方法，该文主要介绍在邻接矩阵存储方式下，利用栈实现对稠密图进行深度优先非递归遍历的算法设计及实现过程。
　　关键词：深度优先；算法；非递归；栈
　　中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）03-0470-03
　　图是一种重要的数据结构，在实际生活中应用非常广泛，如计算机网络、电力网络、交通信号网路等。图可分为有向图，无向图，连通图，非联通图，稠密图，稀疏图等，该文仅以图1为例介绍无向连通稠密图的存储以及基于栈的非递归深度优先遍历算法。
　　1 图的存储表示
　　图在计算机中的物理存储方式主要有邻接矩阵和邻接表两种，其中邻接矩阵适用于稠密图，邻接表适用于稀疏图。该文例图可视为稠密图，因此图的物理存储采用邻接矩阵（二维数组adj[][]）实现，下面是创建邻接矩阵adj[][]的C语言代码：
　　void create_matrix（int adj[V+1][V+1]）
　　{
　　int E，u，v，wgt；//表示边的条数
　　printf（"请输入边数："）；
　　scanf（"%d"，&E）；
　　for（int i=1；i<=E；i++）
　　{
　　printf（"请输入第%d条边"，i）；
　　scanf（"%d %d %d"，&u，&v，&wgt）；
　　adj[u][v]=adj[v][u]=wgt；
　　}
　　}
　　图1利用create_matrix函数建立的邻接矩阵存储示意图如图2所示，我们可以发现图的邻接矩阵是对称矩阵。
　　2 图的深度优先遍历思想
　　深度优先搜索是图的重要遍历方法之一，遍历过程的实质是对每个顶点查找其邻接点的过程，类似于树的先根遍历，具体思路为：
　　1）从图中任一顶点v开始，当顶点v未被访问过时，做访问标记；
　　2）遍历v的所有邻接点：
　　如果邻接点u未被访问过：
　　①输出顶点u；
　　②做访问标记；
　　③遍历u的所有邻接点；
　　为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标记，该文利用数组visited[V]实现，数组初始值设置为0，表示所有顶点均未被访问。
　　3 深度优先遍历的递归算法
　　深度优先遍历的递归算法如下：
　　void DF（int v） //深度优先遍历的递归算法
　　{
　　int u；
　　visited[v] = ++id； //设置顶点v的访问标记
　　printf（"%d—"，v）；
　　for （int t = 1； t <= V； t++） //依次判断图中每个顶点进行如下判断
　　{
　　//如果顶点v、t之间存在边且t未被访问过，则对顶点t进行深度优先遍历；
　　if （adj[v][t] ！= 0 && visited[t] == 0）
　　DF（t）；
　　}
　　}
　　深度优先遍历的递归算法过程清晰、实现简单，在国内大部分数据结构的教材中均采用此种方式介绍深度优先遍历，在教学过程中由于受课时等因素的限制，教师往往也只讲授遍历的递归算法。但由于递归算法的时间效率低下，空间占用量高，在实际应用程序中人们往往采用非递归方式进行深度优先遍历。
　　4 深度优先的非递归算法
　　深度优先的非递归算法需要借助栈实现，算法的基本思路如下：
　　1）初始化栈；
　　2）对所有节点做未访问标记；
　　3）起始节点入栈；
　　4）while栈不为空时：
　　①栈顶顶点v出栈；
　　②如果顶点v未标记为已访问，则
　　打印v；
　　标记v为已访问；
　　遍历顶点v的邻接点，如果邻接点u未被标记为已访问，则u入栈；
　　对于一个含有V个顶点的无向连通图，深度优先遍历的非递归算法在最好的情况下（每个顶点仅有两条边相连）每个顶点仅被访问一次，时间复杂度为O（n）；而在最坏的情况下（图为完全图时），搜索第i层结点时将会有n-i个结点入栈，最多在栈中存储（n-2）*（n-1）/2个结点，此时的时间复杂度与递归算法类似，为O（n2）。
　　深度优先遍历的非递归算法具体程序代码如下：
　　void dfVisit（int v）
　　{
　　SqStack s； //声明一个顺序栈s
　　init（s）； //初始化栈
　　for（int i=1；i<=V；i++）//依次对图中每个顶点设置访问标记
　　visited[i] = 0； //0表示未访问
　　Push（s，v）； //顶点v入栈
　　printf（"DF vertext by iteration："）；
　　while （！isEmpty（s）） //设置循环终止条件为栈空
　　{
　　v =Pop（s）； //用顶点v接收出栈元素
　　if （！visited[v]）//如果顶点v未被访问
　　{
　　printf（"%c—"，v+64）；//打印顶点v
　　visited[v]=++id；//为顶点v设置访问标记
　　for（int u=1；u<=V；u++）//循环用于访问v的每个邻接点u
　　{
　　if （visited[u]==0&&adj[v][u]！=0）//如果顶点v的邻接点u未被访问
　　Push（s，u）；//将邻接点u入栈
　　}//end-for
　　}//end-if
　　}//end-while
　　}
　　利用深度优先遍历的非递归算法dfVisit（）对图1进行遍历时，顶点的遍历顺序及入栈和出栈过程如图3和图4所示。图4中，新入栈的邻接点用斜体和灰色背景表示，如当遍历顶点A的邻接点时，B、C、D、G顶点先后入栈。
　　
　　5 结束语
　　根据图的深度优先遍历定义，我们知道图的深度优先遍历结果不唯一。我们可以设计不同的存储结构来存储和表示图，并在此基础上编写不同的算法进行遍历，进而得到不同的遍历结果。然而当我们基于特定存储结构编写具体遍历算法时，算法的遍历结果却是唯一的，如我们利用本文的dfVisit（）算法对图1进行遍历时，遍历的结果始终是A-G-B-H-F-D-E-C。在学习深度优先遍历算法时，无论是递归算法还是非递归算法，都应该对图的物理存储有一个形象和清晰的认识，因为算法都是在存储结构基础上进行设计和编写的。
　　参考文献：
　　[1] 严蔚敏.数据结构[M].北京：清华大学出版社，1997.
　　[2] 刘中华，张颖超.深度优先搜索的非递归算法[J].科技信息，2010（25）.
　　[3] 魏国辉.DNA计算机中图的深度优先搜索遍历算法[J].计算机工程，2008（15）.
　　[4] 林尚垣.图的深度优先遍历智能化分析与实现[J].海南大学学报：自然科学版，2005（2）.
　　[5] 耿杰.基于深度优先搜索的铁路站场遍历算法研究[J].铁道学报，2012（4）.