广度优先搜索所有路径

Question

首先，谢谢你看这个问题。在

对于学校作业，我们应该创建一个BFS算法并用它来做各种事情。其中之一就是我们应该找到图的根节点和目标节点之间的所有路径。我不知道如何做到这一点，因为我无法找到一种方法来跟踪所有备用路线，而不包括副本/周期。在

这是我的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])

如果能在概念上朝着正确的方向推进，我们将不胜感激。在

如何使用BFS查找两个节点之间的所有路径？在

以下是图表，因为我不知道如何回答杰夫·马卡多的问题。在

^{pr2}$

Answer 1

首先，当你到达目标节点时，你的算法不应该返回，否则你只有一个解。相反，您应该使用一个列表来存储各种解决方案。在

关于算法的核心，请记住，BFS搜索不会一次搜索一条路径，而是全部路径。因此，您不能只在队列中存储一个节点，而是存储一个路径。在

然后只需检查下一个节点是否已经在当前路径中，以添加它以避免循环。如果当前路径的最后一个节点是目标节点，请将其附加到解决方案列表中。在

最后，当队列中不再有不完整路径（=队列为空）时，返回解决方案列表。在