广度优先搜索所有路径 [英] Breadth first search all paths
问题描述
首先，感谢您关注此问题.
First of all, thank you for looking at this question.
对于学校作业，我们应该创建一个BFS算法并将其用于执行各种操作.其中一件事情是，我们应该找到图的根和目标节点之间的所有路径.我不知道如何执行此操作，因为找不到不包含副本/循环的跟踪所有替代路线的方法.
For a school assignment we're supposed to create a BFS algorithm and use it to do various things. One of these things is that we're supposed to find all of the paths between the root and the goal nodes of a graph. I have no idea how to do this as I can't find a way to keep track of all of the alternate routes without also including copies/cycles.
这是我的BFS代码:
def makePath(predecessors, last):
return makePath(predecessors, predecessors[last]) + [last] if last else []
def BFS1b(node, goal):
Q = [node]
predecessor = {node:None}
while Q:
current = Q.pop(0)
if current[0] == goal:
return makePath(predecessor, goal)
for subnode in graph[current[0]][2:]:
if subnode[0] not in predecessor:
predecessor[subnode[0]] = current[0]
Q.append(subnode[0])
在正确方向上的概念性推动将不胜感激.
A conceptual push in the right direction would be greatly appreciated.
tl; dr如何使用BFS查找两个节点之间的所有路径?
tl;dr How do I use BFS to find all of the paths between two nodes?
这里是图表，因为我不确定如何回答Jeff Marcado的问题.
Here is the graph as I'm not sure how to answer Jeff Marcado's question.
graph = { 'A':[366, 3, ('Z', 75 ), ('T', 118), ('S', 140)],
'Z':[374, 2, ('A', 75 ), ('O', 71 )],
'T':[329, 2, ('A', 118), ('L', 111)],
'L':[244, 2, ('T', 111), ('M', 70 )],
'M':[241, 2, ('L', 70 ), ('D', 75 )],
'D':[242, 2, ('M', 75 ), ('C', 120)],
'C':[160, 3, ('D', 120), ('R', 146), ('P', 138)],
'R':[193, 3, ('C', 146), ('P', 97 ), ('S', 80 )],
'S':[253, 4, ('R', 80 ), ('F', 99 ), ('O', 151), ('A', 140)],
'O':[380, 2, ('S', 151), ('Z', 71 )],
'P':[100, 3, ('C', 138), ('R', 97 ), ('B', 101)],
'F':[176, 2, ('S', 99 ), ('B', 211)],
'B':[ 0, 4, ('P', 101), ('F', 211), ('G', 90 ), ('U', 85 )],
'G':[ 77, 1, ('B', 90 )],
'U':[ 80, 3, ('B', 85 ), ('H', 98 ), ('V', 142)],
'H':[151, 2, ('U', 98 ), ('E', 86 )],
'E':[161, 1, ('H', 86 )],
'V':[199, 2, ('U', 142), ('I', 92 )],
'I':[226, 2, ('V', 92 ), ('N', 87 )],
'N':[243, 1, ('I', 87 )],
'W':[400, 1, ('X', 100)],
'X':[400, 1, ('W', 100)],}
推荐答案
首先，到达目标节点时，算法不应返回，否则只有一个解决方案.相反，您应该使用列表来存储各种解决方案.
Firstly, your algorithm should not return when you reach the goal node otherwise you'll have only one solution. Instead, you should use a list to store the various solutions.
关于算法的核心，请记住，一次BFS搜索不会一次探索一条路径，而是一次探索所有路径.因此，您不仅可以将一个节点存储在队列中，还可以存储路径.
Regarding the core of the algorithm, keep in mind that a BFS-search will not explore one path at a time but all. So you cannot just store one node in your queue but rather a path.
然后，您只需检查下一个节点是否不在当前路径中，即可添加该节点以避免循环.如果当前路径的最后一个节点是目标节点，请将其附加到解决方案列表中.
Then you simply check if the next node is not already in your current path to add it to avoid cycles. If the last node of the current path is the goal node, append it to the solution list.
最后，当队列中不再有不完整的路径(==队列为空)时，返回解决方案列表.
Finally, when there is no more incomplete path in the queue (== the queue is empty), return the solution list.
这篇关于广度优先搜索所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
