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

当存在循环时,是否可以使用 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']

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

相似文章

最新文章