《基于栈的非递归深度优先遍历算法设计与实现》由会员分享，可在线阅读，更多相关《基于栈的非递归深度优先遍历算法设计与实现（6页珍藏版）》请在金锄头文库上搜索。
1、基于栈的非递归深度优先遍历算法设计与实现基于栈的非递归深度优先遍历算法设计与实现本文档格式为本文档格式为WORD,WORD,感谢你的阅读。感谢你的阅读。摘要：深度优先遍历是图的一种重要遍历方法，该文主要介绍摘要：深度优先遍历是图的一种重要遍历方法，该文主要介绍 在邻接矩阵存储方式下，利用栈实现对稠密图进行深度优先非在邻接矩阵存储方式下，利用栈实现对稠密图进行深度优先非 递归遍历的算法设计及实现过程。递归遍历的算法设计及实现过程。 关键词：深度优先；算法；非递归；栈关键词：深度优先；算法；非递归；栈 TP311TP311 A A 1009-30441009-3044（20142014）03-04
2、70-0303-0470-03 图是一种重要的数据结构，在实际生活中应用非常广泛，如计图是一种重要的数据结构，在实际生活中应用非常广泛，如计 算机网络、电力网络、交通信号网路等。图可分为有向图，无算机网络、电力网络、交通信号网路等。图可分为有向图，无 向图，连通图，非联通图，稠密图，稀疏图等，该文仅以图向图，连通图，非联通图，稠密图，稀疏图等，该文仅以图1 1 为例介绍无向连通稠密图的存储以及基于栈的非递归深度优先为例介绍无向连通稠密图的存储以及基于栈的非递归深度优先 遍历算法。遍历算法。 1 1 图的存储表示图的存储表示 图在计算机中的物理存储方式主要有邻接矩阵和邻接表两种，图在计算机中的物
3、理存储方式主要有邻接矩阵和邻接表两种， 其中邻接矩阵适用于稠密图，邻接表适用于稀疏图。该文例图其中邻接矩阵适用于稠密图，邻接表适用于稀疏图。该文例图 可视为稠密图，因此图的物理存储采用邻接矩阵（二维数组可视为稠密图，因此图的物理存储采用邻接矩阵（二维数组adad jj）实现，下面是创建邻接矩阵）实现，下面是创建邻接矩阵adjadj的的C C语言代码：语言代码： voidvoid create_matrixcreate_matrix（intint adjV+1V+1adjV+1V+1） intint E E，u u，v v，wgtwgt；/表示边的条数表示边的条数 printfprintf（“
4、“请输入边数：请输入边数：“ “）；）； scanfscanf（“%d“%d“，E E）；）； forfor（intint i=1i=1；i=Ei=E；i+i+） printfprintf（“ “请输入第请输入第%d%d条边条边“ “，i i）；）； scanfscanf（“%d“%d %d%d %d“%d“，wgtwgt）；）； adjuv=adjvu=wgtadjuv=adjvu=wgt； 图图1 1利用利用create_matrixcreate_matrix函数建立的邻接矩阵存储示意图如图函数建立的邻接矩阵存储示意图如图2 2 所示，我们可以发现图的邻接矩阵是对称矩阵。所示，我们可以发现
5、图的邻接矩阵是对称矩阵。 2 2 图的深度优先遍历思想图的深度优先遍历思想 深度优先搜索是图的重要遍历方法之一，遍历过程的实质是对深度优先搜索是图的重要遍历方法之一，遍历过程的实质是对 每个顶点查找其邻接点的过程，类似于树的先根遍历，具体思每个顶点查找其邻接点的过程，类似于树的先根遍历，具体思 路为：路为： 1 1）从图中任一顶点）从图中任一顶点v v开始，当顶点开始，当顶点v v未被访问过时，做访问标未被访问过时，做访问标 记；记； 2 2）遍历）遍历v v的所有邻接点：的所有邻接点： 如果邻接点如果邻接点u u未被访问过：未被访问过： 输出顶点输出顶点u u； 做访问标记；做访问标记； 遍
6、历遍历u u的所有邻接点；的所有邻接点； 为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要 为每个顶点设一个访问标记，该文利用数组为每个顶点设一个访问标记，该文利用数组visitedVvisitedV实现，实现， 数组初始值设置为数组初始值设置为0 0，表示所有顶点均未被访问。，表示所有顶点均未被访问。 3 3 深度优先遍历的递归算法深度优先遍历的递归算法 深度优先遍历的递归算法如下：深度优先遍历的递归算法如下： voidvoid DFDF（intint v v） /深度优先遍历的递归算法深度优先遍历的递归算法 intint u u；
7、 visitedvvisitedv = = +id+id； /设置顶点设置顶点v v的访问标记的访问标记 printfprintf（“%d“%d“ “，v v）；）； forfor （intint t t = = 1 1； t t = V V； t+t+） /依次判断图中每个顶点进行如下判断依次判断图中每个顶点进行如下判断 /如果顶点如果顶点v v、t t之间存在边且之间存在边且t t未被访问过，则对顶点未被访问过，则对顶点t t进行深进行深 度优先遍历；度优先遍历； ifif （adjvtadjvt ！= = 0 0 visitedtvisitedt = 0 0） DFDF（t t）；）；
8、深度优先遍历的递归算法过程清晰、实现简单，在国内大部分深度优先遍历的递归算法过程清晰、实现简单，在国内大部分 数据结构的教材中均采用此种方式介绍深度优先遍历，在教学数据结构的教材中均采用此种方式介绍深度优先遍历，在教学 过程中由于受课时等因素的限制，教师往往也只讲授遍历的递过程中由于受课时等因素的限制，教师往往也只讲授遍历的递 归算法。但由于递归算法的时间效率低下，空间占用量高，在归算法。但由于递归算法的时间效率低下，空间占用量高，在 实际应用程序中人们往往采用非递归方式进行深度优先遍历。实际应用程序中人们往往采用非递归方式进行深度优先遍历。 4 4 深度优先的非递归算法深度优先的非递归算法
9、深度优先的非递归算法需要借助栈实现，算法的基本思路如下深度优先的非递归算法需要借助栈实现，算法的基本思路如下 ： 1 1）初始化栈；）初始化栈； 2 2）对所有节点做未访问标记；）对所有节点做未访问标记； 3 3）起始节点入栈；）起始节点入栈； 4 4）whilewhile栈不为空时：栈不为空时： 栈顶顶点栈顶顶点v v出栈；出栈； 如果顶点如果顶点v v未标记为已访问，则未标记为已访问，则 打印打印v v； 标记标记v v为已访问；为已访问； 遍历顶点遍历顶点v v的邻接点，如果邻接点的邻接点，如果邻接点u u未被标记为已访问，则未被标记为已访问，则u u入入 栈；栈； 对于一个含有对于一个
10、含有V V个顶点的无向连通图，深度优先遍历的非递归个顶点的无向连通图，深度优先遍历的非递归算法在最好的情况下（每个顶点仅有两条边相连）每个顶点仅算法在最好的情况下（每个顶点仅有两条边相连）每个顶点仅 被访问一次，时间复杂度为被访问一次，时间复杂度为O O（n n）；而在最坏的情况下（图为）；而在最坏的情况下（图为 完全图时），搜索第完全图时），搜索第i i层结点时将会有层结点时将会有n-n- i i个结点入栈，最多在栈中存储（个结点入栈，最多在栈中存储（n-2n-2）* *（n-n- 1 1）/2/2个结点，此时的时间复杂度与递归算法类似，为个结点，此时的时间复杂度与递归算法类似，为O O（n
11、2n2） 。 深度优先遍历的非递归算法具体程序代码如下：深度优先遍历的非递归算法具体程序代码如下： voidvoid dfVisitdfVisit（intint v v） SqStackSqStack s s； /声明一个顺序栈声明一个顺序栈s s initinit（s s）；）； /初始化栈初始化栈 forfor（intint i=1i=1；i=Vi=V；i+i+）/依次对图中每个顶点设置访问标记依次对图中每个顶点设置访问标记 visitedivisitedi = = 0 0； /0/0表示未访问表示未访问 PushPush（s s，v v）；）； /顶点顶点v v入栈入栈 printfpr
12、intf（“DF“DF vertextvertext byby iterationiteration：“ “）；）； whilewhile （！（！isEmptyisEmpty（s s） /设置循环终止条件为栈空设置循环终止条件为栈空 v v =Pop=Pop（s s）；）； /用顶点用顶点v v接收出栈元素接收出栈元素 ifif （！（！visitedvvisitedv）/如果顶点如果顶点v v未被访问未被访问 printfprintf（“%c“%c“ “，v+64v+64）；）；/打印顶点打印顶点v v visitedv=+idvisitedv=+id；/为顶点为顶点v v设置访问标记设置
13、访问标记 forfor（intint u=1u=1；u=Vu=V；u+u+）/循环用于访问循环用于访问v v的每个邻接点的每个邻接点u u ifif （visitedu=0visitedu=0adjvuadjvu！=0=0）/如果顶点如果顶点v v的邻接点的邻接点u u未被访问未被访问 PushPush（s s，u u）；）；/将邻接点将邻接点u u入栈入栈 /end-for/end-for /end-if/end-if /end-while/end-while 利用深度优先遍历的非递归算法利用深度优先遍历的非递归算法dfVisitdfVisit（）对图（）对图1 1进行遍历时进行遍历时，顶点
14、的遍历顺序及入栈和出栈过程如图，顶点的遍历顺序及入栈和出栈过程如图3 3和图和图4 4所示。图所示。图4 4中中 ，新入栈的邻接点用斜体和灰色背景表示，如当遍历顶点，新入栈的邻接点用斜体和灰色背景表示，如当遍历顶点A A的的 邻接点时，邻接点时，B B、C C、D D、G G顶点先后入栈。顶点先后入栈。 5 5 结束语结束语 根据图的深度优先遍历定义，我们知道图的深度优先遍历结果根据图的深度优先遍历定义，我们知道图的深度优先遍历结果 不唯一。我们可以设计不同的存储结构来存储和表示图，并在不唯一。我们可以设计不同的存储结构来存储和表示图，并在 此基础上编写不同的算法进行遍历，进而得到不同的遍历结
15、果此基础上编写不同的算法进行遍历，进而得到不同的遍历结果 。然而当我们基于特定存储结构编写具体遍历算法时，算法的。然而当我们基于特定存储结构编写具体遍历算法时，算法的 遍历结果却是唯一的，如我们利用本文的遍历结果却是唯一的，如我们利用本文的dfVisitdfVisit（）算法对（）算法对 图图1 1进行遍历时，遍历的结果始终是进行遍历时，遍历的结果始终是A-G-B-H-F-D-E-A-G-B-H-F-D-E- C C。在学习深度优先遍历算法时，无论是递归算法还是非递归。在学习深度优先遍历算法时，无论是递归算法还是非递归 算法，都应该对图的物理存储有一个形象和清晰的认识，因为算法，都应该对图的物理存储有一个形象和清晰的认识，因为 算法都是在存储结构基础上进行设计和编写的。算法都是在存储结构基础上进行设计和编写的。 参考文献：参考文献： 11 严蔚敏严蔚敏. .数据结构数据结构M
