python - 广度优先搜索所有路径

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])

如果能在概念上插入正确的方向，我们将不胜感激。

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

这是图表，因为我不确定如何回答 Jeff Marcado 的问题。

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)],}

Answer 1

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

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

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

最后，当队列中不再有不完整路径时(==队列为空)，返回解列表。