深度优先搜索实现中的输出不正确

Question

最近在某网站(https://brilliant.org/wiki/depth-first-search-dfs/)看一段深度优先搜索的代码。但是他们的实现并不完全correct.This是他们发布的代码

def depth_first_search(graph):
    visited, stack = set(), [root]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

如您所见，他们应用的逻辑是正确的，但他们使用了设置操作，每次程序运行s 都会更改输出。

这是我的完整程序

graph = {'A': {'B', 'S'}, 'B': {'A'}, 'C': {'S', 'F', 'D', 'E'},
     'D': {'C'}, 'E': {'H', 'C'}, 'F': {'C', 'G'}, 'G': {'S', 'F', 'H'}, 
     'H': {'G', 'E'}, 'S': {'A', 'G', 'C'}}

def depth_first_search(graph, root):
    visited, stack = set(), [root]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

print(depth_first_search(graph, 'A'))

以下是我每次运行程序

得到的输出

{'H', 'C', 'B', 'A', 'D', 'S', 'F', 'E', 'G'}
{'D', 'E', 'C', 'H', 'G', 'S', 'A', 'B', 'F'}
{'G', 'F', 'C', 'H', 'E', 'D', 'B', 'S', 'A'} and so on....

使用 set 的原因对于下面的代码行特别有意义，因为我们希望堆栈仅存储未探索的顶点。

stack.extend(graph[vertex] - visited)

所以执行集合差异操作实现了objective.But它是有代价的above.So我稍微调整了代码以避免使用集合并使用列表

graph = {'A': ['B', 'S'], 'B': ['A'], 'C': ['S', 'F', 'D', 'E'],
 'D': ['C'], 'E': ['H', 'C'], 'F': ['C', 'G'], 'G': ['S', 'F', 'H'],
  'H': ['G', 'E'], 'S': ['A', 'G', 'C']}

def depth_first_search(graph, root):
    visited, stack = [], [root]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.append(vertex)
            neighbours = graph[vertex]
            for neighbour in neighbours:
                # ensures we only add unexplored nodes to the stack
                if neighbour not in visited:
                    stack.append(neighbour)
    return visited

print(depth_first_search(graph, 'A'))

但是我得到了错误的结果

['A', 'S', 'C', 'E', 'H', 'G', 'F', 'D', 'B']

正确的结果一定是

['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']

我做错了什么？

Answer 1

您得到的答案是该图的有效 DFS 订单。似乎有一个不成文的限制，必须按字母顺序遍历节点的邻居。考虑到这一点，有两件事：

首先，您要按照节点的定义顺序将节点的邻居添加到堆栈中。但是当你 pop() 离开堆栈时，你首先从堆栈中取出 last 项。这意味着您正在以相反的顺序选择节点。这很容易通过颠倒迭代邻居的顺序来修复：

for neighbour in reversed(neighbours):

其次，您实际上没有按字母顺序在 graph 中定义节点的邻居。您需要在定义中按字母顺序排列 graph 的值，或者在迭代之前对它们进行排序：

for neighbour in reversed(sorted(neighbours)):
# or
for neighbour in sorted(neighbours, reverse=True):

Answer 2

看起来您的初始代码示例并不是为了生成拓扑排序，而只是为了列出可以从根到达的所有节点。可能重要的是要注意它并没有错，它只是不应该给你一个命令。

您的代码基本上按照它说的去做，并且您得到的输出与您期望的一样正确。只要你想要一个DFS就是。

我认为你缺少的是当你调用 vertex = stack.pop() 时你忘记了它总是 returns 最后一个（即 right-most 元素）并且当你调用stack.append(neighbour)，您正在按从左到右的顺序将 children 压入堆栈。

如果您希望 DFS 专门先进入 "left-most" 分支，那么您需要在将它们添加到堆栈之前反转 neighbours/children 的顺序。

编辑：我还没有足够的代表自由发表评论，但我的回答与 glibdud 的基本相同。您运行遇到的问题似乎是您在头脑中应用了实际上不属于基本 DFS 一部分的额外限制。

深度优先搜索实现中的输出不正确

Incorrect output in Depth First Search Implementation

graph

depth-first-search

python-3.x