Python 队列实现广度搜索算法 附上迷宫实例

from collections import deque
$moze = [
    [1,1,1,1,1,1,1,1,1,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,0,0,1,1,0,0,1],
    [1,0,1,1,1,0,0,0,0,1],
    [1,0,0,0,1,0,0,0,0,1],
    [1,0,1,0,0,0,1,0,0,1],
    [1,0,1,1,1,0,1,1,0,1],
    [1,1,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,1]
];

dirs = [
    lambda x,y:(x+1,y),
    lambda x,y:(x,y+1),
    lambda x,y:(x-1,y),
    lambda x,y:(x,y-1),
]

def moze_path_queue(x1,y1,x2,y2):
    queue = deque() #生成队列用来存储当前可以走的节点
    path = [] #生成列表用来存储已经走过的节点
    queue.append((x1,y1,-1)) #将第一个可以走的节点加入到队列中
    while len(queue) > 0: #如果队列中存在可用节点，那么就需要找下一个可以走的节点，否则就是走到终点了
        cur_node = queue.popleft() #将可用的历史节点 从队列中移除
        path.append(cur_node) #将已经走过的节点放入列表

        if cur_node[0] == x2 and cur_node[1] == y2: #如果当前节点和终点一样 那么迷宫有路 并结束算法
            print_f(path)
            return True

        for dir in dirs: #寻找四个方向的节点
            next_node = dir(cur_node[0],cur_node[1])
            if maze[next_node[0]][next_node[1]] == 0: #如果节点可用那么存储到队列中
                queue.append((next_node[0],next_node[1],len(path) - 1))
                maze[next_node[0]][next_node[1]] = 2 #并且将节点标记为已走过
    return False

#打印路径
def print_f(path):
    real_path = [] #创建真实路径的列表
    i = len(path)-1 #定义列表下标，用于循环路径
    while i>=0:
        real_path.append(path[i][0:2]) #将路径添加到真实路径列表
        i = path[i][2] # 获取路径中所对应的下标
    real_path.reverse() #列表翻转
    for node in real_path:
        print(node) #循环输出路径