首页 > 其他 > 详细

深度优先搜索-overview

时间:2020-06-26 17:02:34      阅读:65      评论:0      收藏:0      [点我收藏+]

技术分享图片

深度优先搜索的实现一般有2种方式

递归

//todo

非递归-借助stack

因为栈后进先出的特点,使其很容易实现树/图的深度优先遍历。如果是BFS,那非递归经常借助queue。
整个过程可以被描述为:

  1. 根结点入栈
  2. 弹出根节点,右节点先入,其次左节点。这样,左节点总是最先被访问到,达到“深”的目的
stack.push(root)
while(stack is not empty):
      get top node
      stack.pop()
      visit top node
      stack.push(left node)
      stack.push(right node)

借助上图,可以容易理解整个过程。

深度优先搜索-overview

原文:https://www.cnblogs.com/zhouyc/p/13195336.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!