BFS、迭代DFS和递归DFS：何时将节点标记为已访问

编程入门行业动态更新时间:2024-10-05 01:16:47

本文介绍了BFS、迭代DFS和递归DFS：何时将节点标记为已访问的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述

在谷歌上搜索了许多小时后，我仍然没有找到关于这个问题的深入、直观和可靠的解决方案。我找到的最接近的文章，链接到某个不知名的论坛上，是这样的：11011110.github.io/blog/2013/12/17/stack-based-graph-traversal.html。我也看到了这个堆栈溢出问题DFS vs BFS .2 differences，但回应没有达成明确的共识。

所以问题是：我在维基百科以及蒂姆·罗加登所介绍的算法中看到，要将BFS实现转换为迭代DFS实现，需要进行以下两个更改：

非递归实现类似于广度优先搜索，但在两个方面不同：它使用堆栈而不是队列，并且它会延迟检查是否已发现顶点，直到顶点从堆栈中弹出，而不是在添加顶点之前进行此检查。

有没有人能通过直觉或例子来解释第二个区别的原因？具体地说：BFS、迭代DFS和递归DFS之间的区别因素是什么，需要将检查推迟到仅针对迭代DFS弹出堆栈之后？

以下是BFS的基本实现：

def bfs(adjacency_list, source): explored = [False] * len(adjacency_list) queue = deque() queue.append(source) explored[source] = True while queue: node = queue.popleft() print(node) for n in adjacency_list[node]: if explored[n] == False: explored[n] = True queue.append(n)

如果我们简单地将队列交换为堆栈，则会得到DFS的以下实现：

def dfs_stack_only(adjacency_list, source): explored = [False] * len(adjacency_list) stack = deque() stack.append(source) explored[source] = True while stack: node = stack.pop() print(node) for n in adjacency_list[node]: if explored[n] == False: explored[n] = True stack.append(n) 这两种算法之间的唯一区别是，我们将BFS中的队列交换为DFS中的堆栈。DFS的这种实现实际上产生了不正确的遍历(在非简单化的图中；对于非常简单的图，它可能无论如何都会产生正确的遍历)。

我相信这就是上面链接的文章中引用的‘错误’。

但是，可以通过以下两种方法之一修复此问题。

这两种实现都会产生正确的遍历：

首先，上面源代码中建议的实现，将检查延迟到从堆栈中弹出节点之后。此实现会在堆栈上产生许多重复项。

def dfs_iterative_correct(adjacency_list, source): explored = [False] * len(adjacency_list) stack = deque() stack.append(source) while stack: node = stack.pop() if explored[node] == False: explored[node] = True print(node) for n in adjacency_list[node]: stack.append(n)

或者，这是一个流行的在线实现(取自Geek for Geek)，它也会生成正确的遍历。堆栈上有一些重复项，但不像以前的实现那样多。

def dfs_geeks_for_geeks(adjacency_list, source): explored = [False] * len(adjacency_list) stack = deque() stack.append(source) while len(stack): node = stack.pop() if not explored[node]: explored[node] = True print(node) for n in adjacency_list[node]: if not explored[n]: stack.append(n) 总而言之，区别似乎不仅仅在于何时检查节点的已访问状态，而更多地在于何时将其实际标记为已访问。此外，为什么将其标记为立即访问对BFS很有效，但对DFS就不行？非常感谢您的真知灼见！

谢谢！

推荐答案

我看不出BFS和DFS在这方面有什么不同。我认为将节点标记为已访问有两个要求：

应而不是阻止将节点邻居推入堆栈或队列。

它应防止将节点再次推送到堆栈或队列中。

这些要求既适用于DFS，也适用于BFS，因此两者的Squance可以是：