Python深度优先搜索(DFS)算法: 生成迷宫及查找所有路径

本文将介绍如何使用Python实现深度优先搜索（DFS）算法来生成随机迷宫，并找到从起点到终点的所有可行路径。

**代码示例：**pythonimport random

设置迷宫大小M = 5N = 5

while True: # 生成迷宫矩阵，1表示墙，0表示通路 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

# 使用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

# 建立邻接表    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

输出迷宫矩阵print('迷宫矩阵:')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()

输出邻接表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

输出所有路径print('

所有路径:')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))

代码讲解:

生成迷宫: - 随机生成一个二维矩阵，用0表示通路，1表示墙壁。 - 保证入口和出口为通路。2. 建立邻接表: - 遍历迷宫矩阵，将每个节点的相邻通路节点存储在邻接表中。3. DFS搜索判断通路: - 从起点开始，递归地探索所有未访问的相邻节点。 - 如果找到终点，则说明存在通路。4. DFS搜索所有路径: - 与判断通路类似，但会记录所有到达终点的路径。

总结:

本文介绍了如何使用Python实现DFS算法来生成迷宫并查找所有路径。DFS算法在解决迷宫问题、图论问题等方面有着广泛的应用。