import randomM = 5N = 5while True # 生成迷宫矩阵 maze = 1 for j in rangeN + 2 for i in rangeM + 2 # 用1初始化所有值相当于墙 for i in range1 M + 1 for j in range1 N + 1 mazeij = randomrandin

这段代码实现了一个随机生成迷宫的程序，并使用深度优先搜索算法检查是否存在通路。如果存在通路，则输出迷宫矩阵、邻接表和所有路径。

以下是具体的代码讲解：

定义迷宫大小

M = 5
N = 5

这里定义了迷宫的大小，这里的迷宫是一个M x N的矩阵。

生成迷宫矩阵

maze = [[1 for j in range(N + 2)] for i in range(M + 2)]
for i in range(1, M + 1):
    for j in range(1, N + 1):
        maze[i][j] = random.randint(0, 1)
maze[1][1] = 0
maze[M][N] = 0

这里生成了一个M+2行，N+2列的矩阵，并将所有的元素都初始化为1，表示墙。然后在矩阵中随机生成0或1，0表示通路，1表示墙。最后将入口和出口的值设为0，表示为通路。

DFS搜索，检查是否存在通路

visited = set()

def dfs_search(start):
    visited.add(start)
    if start == (M, N):
        return True
    for neighbor in adj_list[start]:
        if neighbor not in visited:
            if dfs_search(neighbor):
                return True
    return False

这里定义了一个dfs_search函数，用于搜索从起点是否能到达终点。visited是一个集合，用于记录已经访问过的节点。如果当前节点是终点，则返回True。否则，遍历当前节点的所有邻居节点，如果邻居节点没有被访问过，就递归调用dfs_search函数。如果递归调用返回True，则表示从邻居节点可以到达终点，返回True。如果所有邻居节点都无法到达终点，则返回False。

建立邻接表

adj_list = {}
for i in range(1, M + 1):
    for j in range(1, N + 1):
        if maze[i][j] == 1:
            continue
        neighbors = []
        if i > 1 and maze[i - 1][j] == 0:
            neighbors.append((i - 1, j))
        if i < M and maze[i + 1][j] == 0:
            neighbors.append((i + 1, j))
        if j > 1 and maze[i][j - 1] == 0:
            neighbors.append((i, j - 1))
        if j < N and maze[i][j + 1] == 0:
            neighbors.append((i, j + 1))
        adj_list[(i, j)] = neighbors

这里根据迷宫矩阵建立邻接表。邻接表是一个字典，键为节点，值为该节点的邻居节点列表。如果当前节点为墙，则跳过。否则，遍历当前节点的上下左右四个邻居节点，如果邻居节点是通路，则将其加入当前节点的邻居节点列表中。

检查是否存在通路

if dfs_search((1, 1)):
    break

这里调用dfs_search函数，检查从起点是否能到达终点。如果可以到达，则跳出循环，否则，再次生成迷宫矩阵，继续检查。

输出迷宫矩阵和邻接表

for i in range(1, M + 1):
    for j in range(1, N + 1):
        if maze[i][j] == 0:
            print("0", end=" ")
        else:
            print("1", end=" ")
    print()

for node, neighbors in adj_list.items():
    print(node, '->', neighbors)

这里输出生成的迷宫矩阵和邻接表。

DFS搜索所有路径

def dfs_search_all_paths(start, end, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    if start == end:
        return [[end]]
    paths = []
    for neighbor in adj_list[start]:
        if neighbor not in visited:
            sub_paths = dfs_search_all_paths(neighbor, end, visited)
            if sub_paths:
                for sub_path in sub_paths:
                    paths.append(sub_path + [start])
    return paths

dfs_all_path = dfs_search_all_paths((1, 1), (M, N))
for path in dfs_all_path:
    path.reverse()
    print(" -> ".join(str(step) for step in path))

这里定义了一个dfs_search_all_paths函数，用于搜索从起点到终点的所有路径。visited是一个集合，用于记录已经访问过的节点。如果当前节点是终点，则返回一个包含终点的单元素列表。否则，遍历当前节点的所有邻居节点，如果邻居节点没有被访问过，就递归调用dfs_search_all_paths函数。如果递归调用返回的路径列表非空，则将当前节点加入每个路径的末尾，并将这些路径加入paths列表中。最后返回所有路径。

在主程序中，调用dfs_search_all_paths函数，将起点和终点作为参数传入，得到所有路径，并输出每条路径上的节点