首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

非递归深度优先搜索算法

非递归深度优先搜索(DFS)算法是一种遍历或搜索树或图的算法。与递归DFS相比,非递归DFS使用显式的栈来存储待访问的节点,而不是依赖函数调用栈。这样可以避免递归调用的开销,并且在某些情况下可以更好地控制栈的深度。

以下是非递归DFS算法的基本步骤:

  1. 初始化一个空栈,并将起始节点压入栈中。
  2. 当栈不为空时,执行以下操作: a. 弹出栈顶节点,将其标记为已访问。 b. 访问该节点(例如,打印节点的值或执行其他操作)。 c. 将该节点的所有未访问邻居节点压入栈中。
  3. 重复步骤2,直到栈为空。

以下是一个使用非递归DFS遍历二叉树的示例(假设树节点具有valueleftright属性):

代码语言:javascript
复制
def dfs_iterative(root):
    if not root:
        return

    stack = [root]

    while stack:
        node = stack.pop()
        print(node.value)  # 访问节点

        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

dfs_iterative(root)

这个示例中,我们使用一个栈来存储待访问的节点。我们从根节点开始,将其压入栈中。然后,我们不断弹出栈顶节点并访问它,同时将其未访问的邻居节点压入栈中。这个过程一直持续到栈为空。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

  • 七十九、深度和广度优先搜索算法

    「---- Runsen」 ❞ 深度优先搜索和广度优先搜索作为应用广泛的搜索算法,一般是必考算法。...深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。...根据深度优先搜索的特点,采用递归函数实现比较简单。...对于每一个叶子节点,我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题,可以递归地解决该问题。 DFS,需要把所有的叶子节点的深度进行比较,才可以得到最终的最小深度。...# Related Topics 树 深度优先搜索 方法一:递归(DFS,深度优先搜索) 利用 DFS 找出从根节点到叶子节点的所有路径,只要有任意一条路径的 和 等于 sum,就返回 True。

    57830

    算法06-搜索算法-深度优先搜索

    总结 本系列为C++算法学习系列,会介绍 算法概念与描述,入门算法,基础算法,数值处理算法,排序算法,搜索算法,图论算法, 动态规划等相关内容。本文为搜索算法部分。...大纲要求 【 5 】深度优先搜索 【 5 】广度优先搜索 搜索算法-深度优先搜索 例1:全排列 现假设有n个整数,分别是1~n,现在将这n个数进行排列,每一个整数只能并且一定要出现一次,求它们的全排列...打印完毕之后一定要return,否则程序就会永无止境地进行下去了,也就是要有递归的终止条件。...'; dfs(0); return 0; } //dfs与递归类似 搜索算法-广度优先搜索 在深度优先搜索算法中,是深度越大的结点越先得到扩展。...如果在搜索中把算法改为按结点的层次进行搜索,本层的结点没有搜索处理完时,不能对下层结点进行处理,即深度越小的结点越先得到扩展,也就是说先产生的结点先得以扩展处理,这种搜索算法称为广度优先搜索法。

    19010

    算法:深度、广度优先搜索算法与剪枝-理论

    ---- 深度优先搜索算法(DFS) 百度百科:事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止...简单讲就是一路走到底,再换支路,二叉树的中序遍历就是利用深度优先搜索算法。 我们同样的拿一个二叉树的中序遍历看一看,加深记忆。 ? 如果是图的结构,利用深度优先搜索算法,一定要记住去重,防止死循环。...深度优先搜索算法伪代码 这里只介绍递归的写法,递归内部相当保留一个栈,刚好适合。...= null) dfs(node.right); } 其实就是递归中加多一个判断环路的步骤。建议再看看二叉树中序遍历的递归写法,更能体会出深度优先搜索算法是用栈实现的。...算法中剪枝也是类似概念,当广度或者深度优先搜索算法后面走的路径很多的时候,怎么充分利用资源,把不需要的路径去掉。

    1.7K11

    【数据结构与算法】图遍历算法 ( 深度优先搜索 DFS | 深度优先搜索和广度优先搜索 | 深度优先搜索基本思想 | 深度优先搜索算法步骤 | 深度优先搜索理论示例 )

    文章目录 一、深度优先搜索 DFS 1、深度优先搜索和广度优先搜索 2、深度优先搜索基本思想 3、深度优先搜索算法步骤 二、深度优先搜索示例 ( 理论 ) 1、第一轮递归 2、第二轮递归 3、第三轮递归...4、第四轮递归 5、第五轮递归 6、第六轮递归 7、第七轮递归 一、深度优先搜索 DFS ---- 1、深度优先搜索和广度优先搜索 图 的 遍历 就是 对 图 中的 结点 进行遍历 , 遍历 结点 有如下两种策略...: 深度优先搜索 DFS 广度优先搜索 BFS 2、深度优先搜索基本思想 " 深度优先搜索 " 英文名称是 Depth First Search , 简称 DFS ; DFS 基本思想 : 访问第一个邻接结点..., 该过程是一个递归过程 ; 3、深度优先搜索算法步骤 深度优先搜索算法步骤 : ① 访问初始结点 : 访问 初始结点 v , 并将该 初始结点 v 标记为 " 已访问 " ; ② 查找邻接节点 :..., 将 w 结点 作为 新的 初始结点 v , 从 ① 步骤开始执行 ; 如果 w 结点存在 但是 被访问了 , 那么 查找 w 结点的 下一个 邻接节点 , 转到步骤 ③ 执行 ; 二、深度优先搜索示例

    3.3K20

    广度优先搜索算法(go)

    广度优先搜索算法(Breadth First Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,广度优先搜索算法是从根节点开始,沿着树的宽度遍历树的节点。...借助广度优先搜索算法,可以让你找出两样东西之间的最短距离。 本文通过go语言实现广度优先搜索算法,使用该算法从朋友圈中找出关系最近的售货员朋友。 下面介绍详细的实现过程。...其次,传递创建的朋友圈给breadthFirstSearch函数,该函数是广度优先搜索算法的具体实现,在函数内部,首先取出you的所有朋友,如果朋友数为0,查找失败,返回false。...因为这里的朋友名字是按字母顺序排序,所以优先查找了bob的朋友,而不是claire的朋友,即peggy是朋友圈中距离you最近的售货员朋友。...*/ 参考: 《算法图解》 wiki:广度优先搜索

    2.2K30

    深度优先搜索算法在图论领域的应用与实现

    二、深度优先搜索算法原理深度优先搜索算法的基本思想是从图的某一顶点出发,沿着某一条路径不断向前搜索,直到无法继续为止,然后回溯到上一节点,继续搜索其他路径,直到遍历完整个图。...三、深度优先搜索算法的实现下面通过代码演示实现深度优先搜索算法。假设我们有一个无向图,使用邻接表来表示图的结构。首先,我们定义一个图类,包括图的顶点数量和邻接表。...然后,我们实现深度优先搜索算法递归函数。...深度优先搜索算法可以用来实现拓扑排序。五、深度优先搜索算法的优缺点深度优先搜索算法具有以下优点和缺点:优点:简单易实现:深度优先搜索算法的实现相对简单,递归结构清晰。...节省空间:深度优先搜索算法使用递归栈来保存状态,相比广度优先搜索算法,节省了空间。缺点:不保证找到最优解:深度优先搜索算法没有考虑路径长度,只是通过回溯的方式搜索整个图,因此不能保证找到最优解。

    28530

    广度优先搜索算法(go)

    广度优先搜索算法(Breadth First Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,广度优先搜索算法是从根节点开始,沿着树的宽度遍历树的节点。...借助广度优先搜索算法,可以让你找出两样东西之间的最短距离。 本文通过go语言实现广度优先搜索算法,使用该算法从朋友圈中找出关系最近的售货员。...其次,传递创建的朋友圈给breadthFirstSearch函数,该函数是广度优先搜索算法的具体实现,在函数内部,首先取出you的所有朋友,如果朋友数为0,查找失败,返回false。...因为这里的朋友名字是按字母顺序排序,所以优先查找了bob的朋友,而不是claire的朋友,即peggy是朋友圈中距离you最近的售货员朋友。...*/ 参考: 《算法图解》 wiki:广度优先搜索 LEo at 22:32

    1K50

    漫谈递归递归

    为了防止无穷递归现象,有些语言是规定栈的长度的,比如python语言规定堆栈的长度不能超过1000。还有就是当规模很大的时候,尽量不使用递归,而改为递归的形式,或者优化成尾递归的形式(后面讲)。...递归由于效率低的问题,经常要求转换成循环结构的递归形式。  三:递归转尾递归       有些简单的递归问题,可以不借助堆栈结构而改成循环的递归问题。...很多时候我们需要把递归转化成递归形式,这不仅能让我们加深对递归的理解,而且能提升问题解决的效率。这时候就需要掌握一些转化的技巧,便于我们在用到时信手捏来。      ...一般来说,递归转化为递归有两种情况: 第一种情况:正如第三节所说的递归转尾递归的问题,这类问题可以不借助堆栈结构将递归转化为循环结构。...第二种情况:借助堆栈将递归转化为递归(PS:任何递归都可以借助堆栈转化成递归,第一种情况严格意义上来说不能看做是一种情况)。

    1.8K70

    二叉树的递归遍历(递归递归

    因为树的定义本身就是 递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用递归的方法,就要采用栈去模拟实现。...在三种遍历中, 前序和中序遍历的递归算法都很容易实现,递归后序遍历实现起来相对来说要难一点。 一.前序遍历    前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。  ...);             pre_order(root->rchild);          }     }      2.递归实现     根据前序遍历访问的顺序,优先访问根结点,然后再分别访问左孩子和右孩子...       后序遍历的递归实现是三种遍历方式中最难的一种。...= NULL)               q.push(p->rchild);       }   }  /树的深度 int TreeDepth(BTree* root) {

    1.5K100

    算法06-搜索算法-广度优先搜索

    ,排序算法,搜索算法,图论算法, 动态规划等相关内容。...本文为搜索算法部分。 大纲要求 【 5 】深度优先搜索 【 5 】广度优先搜索 搜索算法-广度优先搜索 广度优先搜索(Breadth-First Search),又称作宽度优先搜索。...广度优先搜索算法(又称宽度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。...-广度优先搜索 在深度优先搜索算法中,是深度越大的结点越先得到扩展。...如果在搜索中把算法改为按结点的层次进行搜索,本层的结点没有搜索处理完时,不能对下层结点进行处理,即深度越小的结点越先得到扩展,也就是说先产生的结点先得以扩展处理,这种搜索算法称为广度优先搜索法。

    34720

    递归遍历树

    先序递归遍历二叉树,中序递归遍历二叉树,后序递归遍历二叉树及双栈法。...先序递归遍历二叉树 先序递归遍历比较简单,感觉与DFS类似,根据先序遍历的规则根左右,先将根节点压入栈,然后遍历左子树,再遍历左子树的左子树,一头走到NULL,把每次遍历的左子树的根节点依次入栈并把当前结点数据打印出来...= Creat(a+1,b,i); T->rchild = Creat(a+i+1,b+i+1,n-i-1); return T; } } return NULL; } //先序递归遍历...Creat(a+1,b,i); T->rchild = Creat(a+i+1,b+i+1,n-i-1); return T; } } return NULL; } //中序遍历递归...单栈法 后序递归遍历和先序中序递归开始类似,先将左子树的左孩子的的左孩子的….每个节点压入栈。

    86810
    领券