当存在循环时，是否有可能遍历图中所有连接的节点?
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数组?
您需要检查给定的节点是否已经在堆栈上，否则您可能最终处理同一个节点两次:
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'的出节点。如果您的图是无向的，则需要确保为每个节点添加了所有正确的条目。如果你的图是定向的，这是预期的行为。
我们也可以优化这段代码。您可以维护一个单独的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']
在将节点放入堆栈时检查它是否被访问，但仅在从堆栈弹出时标记它已访问。这意味着任何在堆栈上的节点都可以被再次推送到堆栈中(因为那时它们还没有被标记为访问过)。
您需要将visited更改为seen或类似的东西，以注意它们已添加到堆栈中，并将next_nodes添加到堆栈中，而不是在访问时添加节点，或者更改next_nodes生成的方式，以便仅获取既不在visited中也不在stack中的节点。
与此无关，出于性能原因，我会将visited设置为set，而不是list。