如何遍历可变长度路径到同一目的地？

Question

我有一个定向网络如下。

现在，我想得到这个图的所有可能的 4 长和 5 长路径（其中起始路径和结束路径都是 B）

4 条长度路径的示例是；

B--C--B--A--B
B--A--B--B--B
B--A--B--C--B

5 条长度路径的示例是；

B--C--B--A--B--B
B--A--B--B--C--B

我尝试使用广度优先搜索 (BFS) 来解决这个问题。 BFS 算法的大部分代码似乎都不能满足我的要求。即;

他们不考虑变长路径
他们的起始节点和结束节点和我的不一样（不同）

我目前的代码如下：

graph = {'A': ['B'],
         'B': ['A','C', 'B'],
         'C': ['B']}

# visits all the nodes of a graph (connected component) using BFS
def bfs_connected_component(graph, start):
   # keep track of all visited nodes
   explored = []
   # keep track of nodes to be checked
   queue = [start]

   # keep looping until there are nodes still to be checked
   while queue:
       # pop shallowest node (first node) from queue
       node = queue.pop(0)
       if node not in explored:
           # add node to list of checked nodes
           explored.append(node)
           neighbours = graph[node]

           # add neighbours of node to queue
           for neighbour in neighbours:
               queue.append(neighbour)
   return explored

bfs_connected_component(graph,'A')

我想知道是否有任何 python 库可供我使用，或者是否有修改 BFS 来解决此问题的方法。

如果需要，我很乐意提供更多示例:)

Answer 1

在搜索所有组合结果时，我发现 python 中的递归生成器与其他方法（例如递归函数或基于堆栈的等价物）相比提供了更紧凑和易于理解的代码。

这里我们正在寻找固定length的从node到goal的所有路径。列表 path 用作累加器，在基本情况下，它成为通过 node.

的 1 路径的前缀

def all_paths(graph, node, goal, length, path=[]):
    if length == 0 and node == goal:
        yield path + [node]
    elif length > 0:
        for n in graph[node]:
            yield from all_paths(graph, n, goal, length - 1, path + [node])

长度为 4 的路径：

>>> print(*all_paths(graph, 'B', 'B', 4), sep='\n')
['B', 'A', 'B', 'A', 'B']
['B', 'A', 'B', 'C', 'B']
['B', 'A', 'B', 'B', 'B']
['B', 'C', 'B', 'A', 'B']
['B', 'C', 'B', 'C', 'B']
['B', 'C', 'B', 'B', 'B']
['B', 'B', 'A', 'B', 'B']
['B', 'B', 'C', 'B', 'B']
['B', 'B', 'B', 'A', 'B']
['B', 'B', 'B', 'C', 'B']
['B', 'B', 'B', 'B', 'B']

长度为 5 的路径：

>>> print(*all_paths(graph, 'B', 'B', 5), sep='\n')
['B', 'A', 'B', 'A', 'B', 'B']
['B', 'A', 'B', 'C', 'B', 'B']
['B', 'A', 'B', 'B', 'A', 'B']
['B', 'A', 'B', 'B', 'C', 'B']
['B', 'A', 'B', 'B', 'B', 'B']
['B', 'C', 'B', 'A', 'B', 'B']
['B', 'C', 'B', 'C', 'B', 'B']
['B', 'C', 'B', 'B', 'A', 'B']
['B', 'C', 'B', 'B', 'C', 'B']
['B', 'C', 'B', 'B', 'B', 'B']
['B', 'B', 'A', 'B', 'A', 'B']
['B', 'B', 'A', 'B', 'C', 'B']
['B', 'B', 'A', 'B', 'B', 'B']
['B', 'B', 'C', 'B', 'A', 'B']
['B', 'B', 'C', 'B', 'C', 'B']
['B', 'B', 'C', 'B', 'B', 'B']
['B', 'B', 'B', 'A', 'B', 'B']
['B', 'B', 'B', 'C', 'B', 'B']
['B', 'B', 'B', 'B', 'A', 'B']
['B', 'B', 'B', 'B', 'C', 'B']
['B', 'B', 'B', 'B', 'B', 'B']

如何遍历可变长度路径到同一目的地？

How to traverse through variable length paths to same destination?

python

breadth-first-search

network-analysis