广度优先搜索所有路径

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 查找两个节点之间的所有路径？

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

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搜索不会一次探索一条路径，而是探索所有路径。因此，您不能只在队列中存储一个节点，而是存储一条路径。

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

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