当存在循环时，是否可以使用 DFS 遍历 graph 中的所有连接节点？
g = {'a':['b','c'],
'b':['a','f'],
'c':['a','f'],
'd':['c','e'],
'e':['d'],
'f':['c','b'],
}
def dfs(graph, node):
stack = [node]
visited = []
while stack:
current = stack.pop()
visited.append(current)
next_nodes = list(filter(lambda x: x not in visited, graph[current]))
stack.extend(next_nodes)
return visited
dfs(g,'a')
>>>
['a', 'c', 'f', 'b', 'b']我的解决方案无法到达 d 或 e。它还访问 b 两次，这很奇怪。如何更改此代码以遍历所有节点（如果可能）而不重复 visited 数组？
回答1
您需要检查给定节点是否已经在堆栈上，否则您可能最终会处理同一节点两次：
def dfs(graph, node):
stack = [node]
visited = []
while stack:
current = stack.pop()
visited.append(current)
next_nodes = list(filter(lambda x: x not in visited + stack, graph[current]))
stack.extend(next_nodes)
return visited至于某些节点未被访问的问题，从 'a' 可达的节点都没有到 'd' 或 'e' 的任何传出邻居。如果您的 graph 是无向的，则需要确保为每个节点添加了所有正确的条目。如果您的 graph 旨在被引导，这是预期的行为。
我们也可以优化这段代码。您可以维护一个单独的 seen 集，以便能够更快地检查您是否已经看到一个节点（看到 == “在堆栈上或已经访问过”）：
def dfs(graph, node):
stack = [node]
seen = {node}
visited = []
while stack:
current = stack.pop()
visited.append(current)
next_nodes = list(filter(lambda x: x not in seen, graph[current]))
stack.extend(next_nodes)
seen.update(next_nodes)
return visited这输出：
['a', 'c', 'f', 'b']回答2
您在将节点放入堆栈时检查它是否被访问，但仅在从堆栈中弹出时才将其标记为已访问。这意味着堆栈上的任何节点都可以再次被推入堆栈（因为此时它们还没有被标记为已访问）。
您需要将 visited 更改为 seen 或类似的东西，以注意它们已添加到堆栈中，并将 next_nodes 添加到其中而不是在访问时添加节点，或者更改方式 <生成 w119> 是为了只获取既不在 visited 也不在 stack 中的节点。
不相关的是，出于性能原因，我会将 visited 设为 set，而不是 list。