锐客网

  1. 首页 > 睿知 > it技术 > >

深度优先搜索（DFS）算法

数据结构IT知识

深度优先搜索（DFS）算法从图G的初始节点开始, 然后逐渐深入, 直到找到目标节点或没有子节点的节点。然后, 该算法从死角回溯到尚未完全开发的最新节点。
DFS中使用的数据结构是堆栈。该过程类似于BFS算法。在DFS中, 导致未访问节点的边缘称为发现边缘, 而导致已访问节点的边缘称为块边缘。
算法

  • 步骤1：G中每个节点的SET STATUS = 1（就绪状态）
  • 步骤2：将起始节点A推入堆栈并设置其STATUS = 2（等待状态）
  • 步骤3：重复步骤4和5, 直到堆栈为空
  • 步骤4：弹出顶部节点N。对其进行处理并设置其STATUS = 3（处理状态）
  • 步骤5：将所有处于就绪状态（状态STATUS = 1）的N个邻居推入堆栈, 并设置其状态= 2（等待状态）[END OF LOOP]
  • 步骤6：退出
范例：
考虑图G及其邻接表, 如下图所示。通过使用深度优先搜索（DFS）算法, 计算从节点H开始打印图的所有节点的顺序。
深度优先搜索（DFS）算法

文章图片
解决方案：
将H推入堆栈
STACK : H

弹出堆栈的顶部元素, 即H, 打印它, 并将H的所有邻居压入就绪状态。
Print H STACK : A

弹出堆栈的顶部元素, 即A, 打印它并将A的所有邻居推入处于就绪状态的堆栈。
Print AStack : B, D

弹出堆栈的顶部元素, 即D, 打印它并将D的所有邻居推入处于就绪状态的堆栈。
Print D Stack : B, F

弹出堆栈的顶部元素, 即F, 将其打印出来并将F的所有邻居推入处于就绪状态的堆栈。
Print FStack : B

弹出栈顶, 即B并推入所有邻居
Print B Stack : C

弹出堆栈顶部, 即C并推入所有邻居。
Print C Stack : E, G

弹出堆栈顶部, 即G并推入所有邻居。
Print GStack : E

弹出堆栈的顶部, 即E并推入其所有邻居。
Print EStack :

因此, 堆栈现在变为空, 并且遍历了图的所有节点。
【深度优先搜索（DFS）算法】图形的打印顺序为：
H → A → D → F → B → C → G → E

    推荐阅读


    上一篇：数据挖掘（决策树归纳）

    下一篇：数据结构之双链表