当存在循环时，是否可以使用 DFS 遍历图中所有连接的节点？

Question

是否可以在存在环的情况下使用DFS遍历图中所有连接的节点？[=15=]

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 数组？

Answer 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

至于某些节点未被访问的问题，none 可从 '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']

Answer 2

你在入栈时检查一个节点是否被访问过，但只有在出栈时才标记它已访问过。这意味着任何 在堆栈上 的节点都可以再次被推入堆栈（因为它们在那个时候还没有被标记为已访问）。

您需要将 visited 更改为 seen 或类似的内容，以注意它们已添加到堆栈中，并将 next_nodes 添加到其中而不是添加访问时的节点，或更改生成 next_nodes 的方式，以便仅采用既不在 visited 也不在 stack.

中的节点

与此无关，出于性能原因，我会将 visited 设为 set，而不是 list。

当存在循环时，是否可以使用 DFS 遍历图中所有连接的节点？

Is it possible to traverse all connected nodes in a graph with DFS when cycles are present?

python

graph

depth-first-search

traversal