Python使用深度优先遍历解决迷宫问题
本文详细介绍如何使用Python语言结合深度优先遍历（DFS）算法解决迷宫寻路问题。通过定义二维列表表示迷宫地图，利用栈（List）的先进后出特性记录路径，实现从起点到终点的自动寻路逻辑。文章包含坐标移动规则、回溯机制及完整可运行代码，帮助开发者理解DFS在路径搜索中的应用。
一、迷宫介绍
在Python中解决迷宫问题，通常将迷宫抽象为一个二维列表。本文将演示如何利用深度优先搜索（DFS）算法来寻找从起点到终点的路径。规则设定为：每次只能向上下左右四个方向移动一步。核心任务是确定起点和终点，并探索是否存在一条连通的路径。
二、深度优先遍历
深度优先遍历的核心思想可以通俗地理解为：选定一条路径一直向前探索，直到遇到死胡同无法前进时，再回溯到上一个节点，重新选择其他未探索的路径继续尝试。
# 1 为墙，0 为路
maze = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 0, 0, 0, 1, 1, 1],
[1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 0, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 0, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
首先，我们需要在代码中明确定义迷宫的起点坐标和终点坐标。
start = (1, 1)
end = (8, 8)
在迷宫地图中，数值0代表可通行的道路，数值1代表墙壁或障碍物。对于任意一个当前坐标点 (r, c)，其相邻四个方向的坐标计算方式如下：
- 向上移动：行号减1，列号不变，即 (r - 1, c)
- 向下移动：行号加1，列号不变，即 (r + 1, c)
- 向左移动：行号不变，列号减1，即 (r, c - 1)
- 向右移动：行号不变，列号加1，即 (r, c + 1)
当算法到达某个点发现四周均为墙壁或已访问过的路径时，即陷入死胡同，此时必须执行回溯操作，原路返回到上一个节点。
为了实现回溯，我们需要引入“栈”（Stack）这一数据结构。栈的核心特性是“先进后出”（Last In, First Out）。
为了直观理解栈的概念，可以类比食堂蒸包子的过程：蒸笼是一层一层叠放的（入栈），最后放入的包子在最上面；当学生取包子时，也是从最上面一层开始取（出栈），即最后放入的包子最先被取出，这体现了先进后出的逻辑。
在Python中，列表（List）天然具备栈的功能。我们可以创建一个空列表，并通过append()方法将元素添加到列表末尾，模拟“入栈”操作。
随后，使用pop()方法从列表末尾取出元素，即可实现“出栈”，取出的总是最后添加的那个元素。
# 定义列表，列表里面放的就是每一步走的坐标，[r, c]
# 第一步就是起始位置，也就是start
list01 = [start]
在算法执行过程中，我们将已经走过的路径标记为2，以此避免重复访问和死循环。
row, col = now
# python 里的解构也叫解包 now包括两个位置，一个行，一个列
maze[row][col] = 2
# 这个代表就是走过的点，为2，因为你走过的路是不能再走的，除了走不通返回的时候，也是为了走不通按原来走过的路原路返回
以下是实现该逻辑的核心代码片段：
if maze[row - 1][col] == 0:
# 上方可以走
list01.append((row - 1, col))
continue
elif maze[row][col + 1] == 0:
# 右方可以走
list01.append((row, col + 1))
continue
elif maze[row + 1][col] == 0:
# 下方可以走
list01.append((row + 1, col))
continue
elif maze[row][col - 1] == 0:
# 左方可以走
list01.append((row, col - 1))
continue
最终完整的可运行代码如下，读者可以直接复制测试：
maze = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 0, 0, 0, 1, 1, 1],
[1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 0, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 0, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
start = (1, 1)
end = (8, 8)
# 定义列表，列表里面放的就是每一步走的坐标，[r, c]
# 第一步就是起始位置，也就是start
list01 = [start]
# 定义循环，让它走
# 列表里最后存的就是下一步走的地方，当前列表有东西才能继续走
while list01:
# 当前走到的节点是哪一个节点，也就是最后走的一步，是哪一步，去列表的最后的一个值就是索引-1
now = list01[-1]
if now == end: # 如果现在的now等于我们之前定义的终点end
print(list01)
print("出来了")
break
row, col = now
# python 里的解构也叫解包 now包括两个位置，一个行，一个列
maze[row][col] = 2
# 这个代表就是走过的点，为2，因为你走过的路是不能再走的，除了走不通返回的时候，也就是为了走不通按原来走过的路原路返回
# continue 结束本次循环，从新开始判断走路
if maze[row - 1][col] == 0:
# 上方可以走
list01.append((row - 1, col))
continue
elif maze[row][col + 1] == 0:
# 右方可以走
list01.append((row, col + 1))
continue
elif maze[row + 1][col] == 0:
# 下方可以走
list01.append((row + 1, col))
continue
elif maze[row][col - 1] == 0:
# 左方可以走
list01.append((row, col - 1))
continue
else: # 走不通过，直接循环干掉每一步，重新调整路线
list01.pop()
else:
print("这个迷宫走不通")
总结
至此，关于Python使用深度优先遍历解决迷宫问题的介绍已完成。如需了解更多Python深度优先搜索相关内容，建议查阅本站过往文章或继续浏览后续教程，感谢支持！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
