Python实战开发及案例分析（22）—— 深度优先，Python实战开发及案例分析（深度优先探索）

温馨提示：这篇文章已超过438天没有更新，请注意相关的内容是否还可用！

摘要：本文介绍了Python实战开发及案例分析的第22部分——深度优先。文章详细阐述了深度优先搜索（DFS）算法的原理和实现过程，并通过实际案例展示了其在解决实际问题中的应用。通过学习和实践，读者可以掌握深度优先搜索算法的核心思想，提高Python编程能力，并学会将其应用于实际项目中。

深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。与广度优先搜索不同，深度优先搜索尽可能深地遍历图的分支，直到找到目标或达到死胡同后才回溯。DFS可以使用递归实现或利用栈来进行非递归实现。

Python实战开发及案例分析（22）—— 深度优先，Python实战开发及案例分析（深度优先探索）第1张

（图片来源网络，侵删）

Python中的DFS实现

以下是使用Python实现深度优先搜索的两种方式：递归和非递归（使用栈）。

图的定义

首先，定义一个图，这里使用字典来实现，其中键是节点，值是与该节点直接相连的节点列表。

Python实战开发及案例分析（22）—— 深度优先，Python实战开发及案例分析（深度优先探索）第2张

（图片来源网络，侵删）

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['G'],
    'F': [],
    'G': []
}

递归实现DFS

递归是实现DFS的一种直观方式。

def dfs_recursive(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    print(vertex, end=' ')  # 处理节点，这里是打印节点
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
# 调用DFS函数
dfs_recursive(graph, 'A')

非递归实现DFS

非递归实现使用栈来模拟递归过程。

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            print(vertex, end=' ')
            visited.add(vertex)
            # 将邻接节点逆序压栈，以保持与递归版本相同的遍历顺序
            stack.extend(reversed(graph[vertex]))
# 调用DFS函数
dfs_iterative(graph, 'A')

案例分析：迷宫寻路问题

假设有一个迷宫，表示为一个二维网格，其中1代表墙壁，0代表可通行区域。我们需要找到从起点到终点的路径。

迷宫定义

maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 0, 0]
]

DFS求解迷宫

使用DFS找到从左上角到右下角的一条路径。

def dfs_maze(maze, start, goal):
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 可移动方向（右，下，左，上）
    stack = [(start, [start])]
    visited = set([start])
    while stack:
        (x, y), path = stack.pop()
        if (x, y) == goal:
            return path
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0