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

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

是否可以在存在环的情况下使用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']

我的解决方案无法达到 de。它还访问了 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

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

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

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

中的节点

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