开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

非递归深度优先搜索算法

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

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

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

以下是一个使用非递归DFS遍历二叉树的示例（假设树节点具有value、left和right属性）：

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)

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

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

图的深度优先和广度优先算法（DFS递归与非递归）

本博客前面文章已对图有过简单的介绍，本文主要是重点介绍有关图的一些具体操作与应用阅读本文前，可以先参考本博客各种基本算法实现小结（四）—— 图及其遍历和图的一些基本算法无向图——邻接矩阵的深度优先和广度优先算法实现

1.9K5 0

树与二叉树的深度优先与广度优先算法（递归与非递归）

本博客前面文章已对树与二叉树有过简单的介绍，本文主要是重点介绍有关二叉树的一些具体操作与应用阅读本文前，可以先参考本博客各种基本算法实现小结（三）—— 树与二叉树和各种基本算法实现小结（二）—— 堆栈二叉树深度层数...、叶子数、节点数和广度优先算法以及树的先序、中序、后序的递归与非递归（深度优先）测试环境：VS2008（C） #include "stdafx.h" #include <stdlib.h

8202 0

深度搜索算法查找最短路径的方法_深度优先搜索算法

从图中可以得到一个5*5的二维矩阵，利用深度搜索算法，求出最短路径。

1.9K6 0

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

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

5743 0

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

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

1811 0

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

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

1.6K1 1

算法：深度、广度优先搜索算法与剪枝-实战

用广度优先搜索算法简单。...node.right); } lists.add(list); } return lists; } 方法二：DFS 深度优先搜索也是可以的...二叉树的最大深度 ? 题解：也是搜索问题，只是搜索结束条件要看清楚，是当前节点没有左右节点时为最大深度。也就是一个深度优先搜索算法。...并不需要考虑左右节点 public int maxDepth(TreeNode root) { if (root == null) return 0; /递归出口...二叉树的最小深度 ? 方法一：DFS 这个和上一题有区别在于，max改为min也不行，当9有左节点没有右节点的时候，还会返回1。当前节点只有一侧节点时，上一题解法就错误了。

6232 0

【数据结构与算法】图遍历算法 ( 深度优先搜索 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.2K2 0

广度优先搜索算法（go）

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

2.2K3 0

DFS：从递归去理解深度优先搜索

一、深入理解递归二、递归vs迭代三、深入理解搜索、回溯和剪枝四、汉诺塔问题 . - 力扣（LeetCode） class Solution { public: //笔试题，不讲武德，C=A...ans*=x;//说明最低位为1，要乘以x x*=x; n>>=1; } return ans; } }; 2、递归

1091 0

广度优先搜索算法（go）

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

1K5 0

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

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

2733 0

漫谈递归转非递归

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

1.8K7 0

归并排序(递归+非递归)

归并排序递归 1.基本思想主要使用了分治思想即大事化小，先使每个子序列有序，子使序列段有序，将两个有序表合并成一个有序表 2....使用两个函数完成归并因为想要malloc只开辟一块空间，而不是设置在mergesort1函数中每递归一次开辟一块空间,极大节省开辟空间开销 3....递归结束条件当下标 left 与right 相等时，正好为一个数，即 return 返回当数组为0，就会发生 left>right，区间不存在 4.时间复杂度与空间复杂度计算 1....归并排序非递归 1....代码 void mergesortNonR(int* a, int n)//归并排序非递归 { int* tmp = (int*)malloc(sizeof(int) * n); if

4931 0

二叉树的非递归遍历（递归和非递归）

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

1.5K10 0

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

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

3302 0

二叉树的非递归深度遍历

二叉树的非递归深度遍历使用栈 while（p || !

3773 0

全排列(递归与非递归实现)

全排列问题在公司笔试的时候非经常见，这里介绍其递归与非递归实现。...递归算法 1、算法简述简单地说：就是第一个数分别以后面的数进行交换 E.g：E = （a , b , c），则 prem（E）= a.perm（b,c）+ b.perm（a,c）+ c.perm（...a,b）然后a.perm（b,c）= ab.perm（c）+ ac.perm（b）= abc + acb.依次递归进行。...Perm(pszStr, begin + 1, end); swap(pszStr , begin, i); } } } 非递归算法

6862 0

递归和非递归分别实现strlen

1.递归方法实现 #include #include int Strlen(char str[]){ if(str[0]=='\0'){ return 0;}...char str[] = "hehe"; int len = Strlen(str); printf("%d\n",len); system("pause"); return 0; } 2.非递归方法实现

3462 0

非递归遍历树

先序非递归遍历二叉树，中序非递归遍历二叉树，后序非递归遍历二叉树及双栈法。...先序非递归遍历二叉树先序非递归遍历比较简单，感觉与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; } //中序遍历非递归...单栈法后序非递归遍历和先序中序非递归开始类似，先将左子树的左孩子的的左孩子的….每个节点压入栈。

8641 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭