Dfs与Bfs混淆
来自topcoder的一篇文章：
“在BFS中，我们在将顶点推入队列时标记访问的顶点，而不是在DFS中弹出顶点时标记访问的顶点。”
注意：这是在使用显式堆栈（伪dfs）实现dfs时说的。
我的问题是为什么会这样？为什么我们不能在从队列弹出后标记访问的顶点，而在bfs的情况下推到队列上？
共有1个答案
您的困惑可能来自于对树的思考太多，但是BFS和DFS可以在任何图形上运行。例如，考虑一个带有循环的代码：<代码> AB B-C-A。如果从A开始选择宽度优先，则首先将B和C添加到列表中。然后，您将弹出B，除非它们被标记为已访问，否则您将在列表中添加C和A，这显然是错误的。如果您先从A，然后访问B，再从那里访问C，然后访问A，除非A已标记为已访问。
总之，无论采用哪种算法，只要第一次看到顶点，就需要将其标记为可见。但是，如果你只考虑DAGs，你会发现事情变得简单一点，因为在那里你没有像上面那样的循环。不管怎么说，关键是你不会陷入一个循环中，而且有多种变体。设置标志是一种方式，检查访问的顶点集是另一种方式，在某些情况下，如树，您不需要做任何事情，只需按顺序迭代边。
-
根据维基百科，DFS和BFS的实现基本上有两种不同。 它们是： 1）DFS使用堆栈，而BFS使用队列。（我理解这一点）。 2）DFS延迟检查是否发现顶点，直到顶点从堆栈中弹出，而不是在推动顶点之前进行此检查。 我不能理解第二个区别。我的意思是为什么DFS在从堆栈中删除后访问节点，而BFS在将节点添加到队列之前访问节点。 谢谢 额外信息： 在上述两种算法的一个简单实现中，我们使用一个布尔数组（让我们
-
我正在研究一般图的非递归DFS和BFS。除了前者使用堆栈而不是队列之外，唯一的区别在于它“延迟检查顶点是否已被发现，直到顶点从堆栈中弹出，而不是在推送顶点之前进行此检查”。为什么此“访问”检查顺序不同？或者换句话说，我们可以通过简单地用堆栈替换BFS中的队列来将BFS更改为非递归DFS吗？ 我检查了所有我能找到的帖子，比如这个和这个，但是没有一个能澄清这个问题。
-
本文向大家介绍BFS和DFS的实现思想相关面试题，主要包含被问及BFS和DFS的实现思想时的应答技巧和注意事项，需要的朋友参考一下 参考回答： BFS:(1)顶点v入队列(2)当队列为非空时继续执行否则停止(3)从队列头取顶点v,查找顶点v的所有子节点并依次从队列尾插入(4)跳到步骤2 DFS:(1)访问顶点v并打印节点(2)遍历v的子节点w,若w存在递归的执行该节点。
-
任何人都可以提供代码，伪代码，甚至提供良好的链接来实现DFS（深度优先搜索）和BFS（广度优先搜索）在普通JavaScript（没有JQuery，或任何帮助程序库）中？我一直在试图了解如何实现任一遍历，但我似乎无法真正区分 BFS 和 DFS 实现的区别。 如果我们想要一个具体问题作为示例：我想在给定节点上遍历 DOM，并获取所有类名。 （我认为遍历的唯一方法是遍历每个父节点，从该节点获取我需要的
-
我是一名本科生，正在读《科曼简介》。准备第三次考试，准备期末考试。 在第22章（第603页）中，它讨论了DFS如何将前置子图作为森林生成，以及BFS如何将前置子图作为树生成。我只是不明白。 我的想法是： 如果顶点v可以从一个开始搜索的源顶点s到达，那么顶点v是否有一些前身（可能是不同的，但存在），而不管在输入图上运行DFS或BFS？也就是说，DFS和BFS都可以访问它。 如果是这样，为什么DFS可
-
查看BFS和DFS算法，它们似乎将节点标记为已访问。如果我只在树中导航，我的实现是否仍然需要将节点标记为已访问？我想对每个节点执行一次操作。 它似乎只适用于存在循环的图形，这样我就有可能两次碰到同一个节点。如果我递归地对一棵树进行调用，那么似乎不需要具有已访问状态，因为在堆栈中的所有调用返回到当前节点之后，我可以选择在节点上执行我想要的操作。我的假设正确吗？ 谢谢