如何在字典表示的8×8迷宫中用BFS算法追踪实际路径？

要追踪BFS找到的实际路径，核心是记录每个节点的父节点，或者在队列中存储完整路径。这里推荐父节点记录法，空间效率更高。

修改后的代码实现 #

#--- Clear Terminal
import os
clear = lambda: os.system('cls')
clear()

import collections

paths = {   (0, 0): {'U': False, 'D': True, 'L': False, 'R': True}, 
            (0, 1): {'U': False, 'D': False, 'L': True, 'R': True}, 
            (0, 2): {'U': False, 'D': True, 'L': True, 'R': False}, 
            (0, 3): {'U': False, 'D': False, 'L': False, 'R': True}, 
            (0, 4): {'U': False, 'D': False, 'L': True, 'R': True}, 
            (0, 5): {'U': False, 'D': False, 'L': True, 'R': True}, 
            (0, 6): {'U': False, 'D': False, 'L': True, 'R': True}, 
            (0, 7): {'U': False, 'D': True, 'L': True, 'R': False}, 
            (1, 0): {'U': True, 'D': True, 'L': False, 'R': False}, 
            (1, 1): {'U': False, 'D': False, 'L': False, 'R': False}, 
            (1, 2): {'U': True, 'D': True, 'L': False, 'R': False}, 
            (1, 3): {'U': False, 'D': True, 'L': False, 'R': True}, 
            (1, 4): {'U': False, 'D': True, 'L': True, 'R': False}, 
            (1, 5): {'U': False, 'D': False, 'L': False, 'R': True}, 
            (1, 6): {'U': False, 'D': True, 'L': True, 'R': False}, 
            (1, 7): {'U': True, 'D': True, 'L': False, 'R': False}, 
            (2, 0): {'U': True, 'D': False, 'L': False, 'R': True}, 
            (2, 1): {'U': False, 'D': False, 'L': True, 'R': True}, 
            (2, 2): {'U': True, 'D': True, 'L': True, 'R': True}, 
            (2, 3): {'U': True, 'D': False, 'L': True, 'R': False}, 
            (2, 4): {'U': True, 'D': True, 'L': False, 'R': False}, 
            (2, 5): {'U': False, 'D': True, 'L': False, 'R': True}, 
            (2, 6): {'U': True, 'D': True, 'L': True, 'R': True}, 
            (2, 7): {'U': True, 'D': True, 'L': True, 'R': False}, 
            (3, 0): {'U': False, 'D': True, 'L': False, 'R': True}, 
            (3, 1): {'U': False, 'D': False, 'L': True, 'R': True}, 
            (3, 2): {'U': True, 'D': False, 'L': True, 'R': False}, 
            (3, 3): {'U': False, 'D': True, 'L': False, 'R': True}, 
            (3, 4): {'U': True, 'D': False, 'L': True, 'R': False}, 
            (3, 5): {'U': True, 'D': True, 'L': False, 'R': False}, 
            (3, 6): {'U': True, 'D': True, 'L': False, 'R': False}, 
            (3, 7): {'U': True, 'D': True, 'L': False, 'R': False}, 
            (4, 0): {'U': True, 'D': True, 'L': False, 'R': False}, 
            (4, 1): {'U': False, 'D': True, 'L': False, 'R': True}, 
            (4, 2): {'U': False, 'D': False, 'L': True, 'R': True}, 
            (4, 3): {'U': True, 'D': False, 'L': True, 'R': False}, 
            (4, 4): {'U': False, 'D': False, 'L': False, 'R': True},
            (4, 5): {'U': True, 'D': True, 'L': True, 'R': False}, 
            (4, 6): {'U': True, 'D': False, 'L': False, 'R': False}, 
            (4, 7): {'U': True, 'D': True, 'L': False, 'R': False}, 
            (5, 0): {'U': True, 'D': False, 'L': False, 'R': False}, 
            (5, 1): {'U': True, 'D': True, 'L': False, 'R': False}, 
            (5, 2): {'U': False, 'D': True, 'L': False, 'R': True}, 
            (5, 3): {'U': False, 'D': True, 'L': True, 'R': False}, 
            (5, 4): {'U': False, 'D': False, 'L': False, 'R': True}, 
            (5, 5): {'U': True, 'D': True, 'L': True, 'R': True}, 
            (5, 6): {'U': False, 'D': True, 'L': True, 'R': True}, 
            (5, 7): {'U': True, 'D': True, 'L': True, 'R': False}, 
            (6, 0): {'U': False, 'D': True, 'L': False, 'R': False}, 
            (6, 1): {'U': True, 'D': False, 'L': False, 'R': True}, 
            (6, 2): {'U': True, 'D': False, 'L': True, 'R': False}, 
            (6, 3): {'U': True, 'D': True, 'L': False, 'R': True}, 
            (6, 4): {'U': False, 'D': False, 'L': True, 'R': True}, 
            (6, 5): {'U': True, 'D': False, 'L': True, 'R': False}, 
            (6, 6): {'U': True, 'D': True, 'L': False, 'R': True}, 
            (6, 7): {'U': True, 'D': True, 'L': True, 'R': False}, 
            (7, 0): {'U': True, 'D': False, 'L': False, 'R': True}, 
            (7, 1): {'U': False, 'D': False, 'L': True, 'R': True}, 
            (7, 2): {'U': False, 'D': False, 'L': True, 'R': True}, 
            (7, 3): {'U': True, 'D': False, 'L': True, 'R': True}, 
            (7, 4): {'U': False, 'D': False, 'L': True, 'R': True}, 
            (7, 5): {'U': False, 'D': False, 'L': True, 'R': True}, 
            (7, 6): {'U': True, 'D': False, 'L': True, 'R': False}, 
            (7, 7): {'U': True, 'D': False, 'L': False, 'R': False}}

start = (5, 5)
end = (2, 2)

queue = collections.deque()
queue.append(start)
seen = set([start])
# 新增父节点字典，记录每个节点的来源
parent = {}
found = False

while queue:
    current = queue.popleft()
    i, j = current
    
    if current == end:
        found = True
        break

    #--- check up
    if paths[(i, j)]["U"] and (i - 1, j) not in seen:
        next_node = (i - 1, j)
        queue.append(next_node)
        seen.add(next_node)
        parent[next_node] = current

    #--- check Down
    if paths[(i, j)]["D"] and (i + 1, j) not in seen:
        next_node = (i + 1, j)
        queue.append(next_node)
        seen.add(next_node)
        parent[next_node] = current

    #--- check Left
    if paths[(i, j)]["L"] and (i, j - 1) not in seen:
        next_node = (i, j - 1)
        queue.append(next_node)
        seen.add(next_node)
        parent[next_node] = current

    #--- check Right（修正原代码的注释错误）
    if paths[(i, j)]["R"] and (i, j + 1) not in seen:
        next_node = (i, j + 1)
        queue.append(next_node)
        seen.add(next_node)
        parent[next_node] = current

# 回溯父节点构建路径
if found:
    path = []
    current = end
    while current != start:
        path.append(current)
        current = parent[current]
    path.append(start)
    # 反转路径得到从起点到终点的顺序
    path.reverse()
    print("找到的路径：")
    print(path)
else:
    print("不存在从起点到终点的路径")

关键修改说明 #

• 添加parent字典：每个新访问的节点都记录它的上一个节点（父节点），用于后续回溯路径。
• 找到终点后，从终点开始反向遍历parent字典，直到回到起点，再反转路径得到从起点到终点的顺序。
• 修正了原代码中右侧检查的注释错误（重复写了"check Left"）。

参考资料 #

我参考的BFS资料：《Python中的迷宫问题》

内容的提问来源于stack exchange，提问作者LukiRoth