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

问题描述

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

所以问题是： 我在维基百科以及蒂姆·罗加登所介绍的算法中看到，要将BFS实现转换为迭代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)

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

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

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

    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在这方面有什么不同。 我认为将节点标记为已访问有两个要求：

应而不是阻止将节点邻居推入堆栈或队列。 它应防止将节点再次推送到堆栈或队列中。

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

从堆栈或队列获取节点 将节点标记为已访问 获取节点的邻居 将任何未访问的邻居放入堆栈或队列