广度优先搜索，图中目标的所有路径

Question

我一边玩 BFS，一边尝试自学 Python 3. 目前我正在尝试在图表中获取从开始到目标的所有路径。

图表设置如下：

graph = {
    A : [B, C],
    B : [D, E],
    C : [F],
    F : [B]
}

所以，有一条从 F 到 B 的路径。我运行遇到的问题如下：由于某些节点设置为访问，算法无法运行再次超过他们。当然，我可以更改它，但我想知道我应该使用什么 'stop' 条件。

我的代码是这样的：

initial = A
goal = D 
# So there are 2 routes: 
#   A -> C -> F -> B -> D
#   A -> B  -> D

frontier = queue.Queue()
frontier.put(initial)

backtracker = { }
paths = []

# until I find a halting condition.    
while True:

    node = frontier.get()
    print('Popping: ' + node.name)

    node.isOpen = False

    if node in graph:
        for child in graph[node]:
            print('Expanding: ' + node.name + ' -> ' + child.name)

            backtracker.update( { child : node } )

            if child.name == goal.name:
                path = backtrack(backtracker, initial, goal)
                paths.append(path)

                backtracker = {}
                goal.isOpen = True
                initial.isOpen = True
                frontier = queue.Queue()
                frontier.put(initial)

            if child.isOpen:
                print('Putting: ' + child.name)
                frontier.put(child)

所以在这种情况下，找到了路径 A -> B -> D，但这将 B 设置为关闭，因此算法无法再访问它来查找 A -> C -> F -> B -> D. 我开始绕圈子思考，所以任何提示（而不是提示然后是完整的解决方案！！！）将不胜感激。

让我们忽略 'A -> C -> F -> B -> A -> C -> F -> B -> D' 等情况（无论如何这是不可能的，因为没有定义从 B -> A 的路径）。

Answer 1

BFS 尝试构建生成树。如果你想在过程中得到最短路径，你可以在第一次找到目标节点时停止——这是BFS的典型用例。

但是如果你想找到所有条路径，我认为停止条件是~~你已经访问了所有节点，所以生成树是完整的~~ 从您已经访问过的节点中没有您可以访问的其他节点。你不能早点停下来，因为即使是你要访问的最后一个节点，也可能有一条通向目标节点的单向边，揭示了一条新路径（尽管是最不理想的路径）。

在写上面的答案时，我可能只是部分理解了问题。如果你问的是最后生成路径，并给出类似

的配置

 A--------->B-------->C
  \       /  \       /
   \->D->/    \->E->/

你想找到所有的 ABC、ADBC、ABEC 和 ADBEC，我想你需要用递归的方式对这个 valid-paths-graph 做一个完整的遍历，一个 DFS（就在这个 sub-graph，所有可能的尝试都会生成一个有效路径）。因此 BFS-pass 可用于将原始图缩减为仅包含实际（可能是冗余）路径的图，但随后需要 DFS 来实际单独生成所有路径。

广度优先搜索，图中目标的所有路径

Breath first search, all paths to a goal in a graph

python

algorithm

graph-algorithm