深度优先搜索（DFS）是图遍历的核心算法之一，本文通过生活化案例揭示其"一条路走到底"的特性，详细讲解递归与非递归实现，并提供可运行的代码示例和复杂度分析。

一、什么是深度优先搜索？

想象你正在玩迷宫游戏，选择最左边的路径一直走到尽头，遇到死路就退回上一个岔路口——这正是DFS的核心思想。作为图遍历的经典算法，DFS遵循"深度优先"原则，沿着某条分支不断深入直到无法继续，再回溯探索其他分支。

算法特性

1. 纵向探索：优先访问新发现的节点
2. 递归本质：天然适合递归实现
3. 回溯特性：需要记录访问状态
4. 栈结构：显式/隐式使用栈保存路径

与广度优先搜索（BFS）的"地毯式搜索"不同，DFS更适合解决连通性问题、拓扑排序、寻找所有解等场景。

二、DFS的运作机制

基本流程

1. 从起始节点开始访问
2. 标记该节点为已访问
3. 递归访问其未探索的相邻节点
4. 当没有未访问的邻居时回溯

python

递归版DFS伪代码

def dfs(node):
visited.add(node)
for neighbor in node.neighbors:
if neighbor not in visited:
dfs(neighbor)

时间复杂度分析

• 邻接表表示：O(V+E)
• 邻接矩阵表示：O(V²)
  其中V为顶点数，E为边数

三、DFS的代码实现

递归实现（推荐）

python
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=' ') # 处理节点

for neighbor in graph[node]:
    if neighbor not in visited:
        dfs_recursive(graph, neighbor, visited)

示例图（邻接表）

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

dfs_recursive(graph, 'A') # 输出: A B D E F C

非递归实现（栈模拟）

python
def dfs_iterative(graph, start):
visited = set()
stack = [start]

while stack:
    node = stack.pop()
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        # 逆序压栈保证访问顺序
        stack.extend(reversed(graph[node]))

dfs_iterative(graph, 'A') # 输出: A C F B E D

处理非连通图

python def dfs_disconnected(graph): visited = set() for node in graph: if node not in visited: dfs_recursive(graph, node, visited)

四、DFS的典型应用场景

1. 路径查找：迷宫求解、国际象棋走法计算
2. 连通性检测：判断图中是否存在通路
3. 拓扑排序：课程安排、任务调度
4. 回溯算法：八皇后问题、数独求解
5. 组件标记：识别图中的连通分量

五、DFS的优化技巧

1. 剪枝策略：在搜索树中提前终止无效分支
2. 记忆化搜索：存储已计算的结果避免重复
3. 迭代深化：限制搜索深度逐步扩展
4. 双向DFS：从起点和终点同时搜索

python

带路径记录的DFS改进版

def dfs_path(graph, start, end, path=None):
if path is None:
path = []
path = path + [start]

if start == end:
    return [path]

paths = []
for neighbor in graph[start]:
    if neighbor not in path:
        new_paths = dfs_path(graph, neighbor, end, path)
        paths.extend(new_paths)
return paths

print(dfs_path(graph, 'A', 'F'))

输出: [['A', 'B', 'E', 'F'], ['A', 'C', 'F']]

六、DFS的局限性

1. 可能陷入深度分支导致效率低下
2. 非最优解：首次找到的路径不一定最短
3. 递归实现可能引发栈溢出
4. 需要合理设置访问标记避免重复计算