Python算法基础篇之深度优先搜索（DFS）

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

深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索图、树的算法。其核心策略是：从起始节点出发，沿着一条路径尽可能深入地探索，直到无法继续为止，然后回溯到上一个节点继续探索其他分支。

1.1 核心思想（三步走）

1. 深入：从起始节点出发，沿着一条路径一直走到尽头
2. 回溯：遇到死胡同（无未访问邻居）时，退回上一个节点
3. 重复：继续探索其他分支，直到所有节点都被访问

1.2 形象比喻

想象你在一个巨大的迷宫中探险：

• 你总是选择一条岔路一直走到底
• 遇到死路就原路返回到上一个岔路口
• 选择另一条没走过的岔路继续探索
• 直到走遍迷宫的每一个角落

这就是DFS的精髓——“不撞南墙不回头”。

1.3 DFS遍历过程图解

下面是一张DFS遍历过程的示意图，展示了DFS如何沿着一条路径深入探索：

如上图所示，DFS从节点A出发，优先选择一条路径深入（A → C → B），走到尽头后回溯，再探索其他分支（C → D → F → G → E）。

二、DFS的数据结构支撑：栈（Stack）

DFS的实现依赖于栈（Stack）这种数据结构。

2.1 栈的特性

栈是一种后进先出（LIFO, Last In First Out）的数据结构：

• 最后放入的元素最先被取出
• 就像一摞盘子，只能从最上面取放

2.2 DFS与栈的关系

DFS有两种实现方式，都与栈有关：

三、递归实现DFS

3.1 图的DFS遍历（递归版）

# 图的DFS遍历 - 递归实现defdfs_recursive(graph,start,visited=None):ifvisitedisNone:visited=set()# 访问当前节点print(start,end=' ')visited.add(start)# 递归访问所有未访问的邻居节点forneighboringraph.get(start,[]):ifneighbornotinvisited:dfs_recursive(graph,neighbor,visited)returnvisited# 构建示例图（邻接表表示）graph={'A':['B','C'],'B':['A','D','E'],'C':['A','F','G'],'D':['B'],'E':['B','H'],'F':['C'],'G':['C'],'H':['E']}print("="*50)print("【示例1】图的DFS递归遍历")print("="*50)print("图结构:",graph)print(" DFS遍历顺序（从A开始）:")visited_nodes=dfs_recursive(graph,'A')print(f" 已访问节点:{visited_nodes}")

运行结果：

================================================== 【示例1】图的DFS递归遍历 ================================================== 图结构: {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F', 'G'], 'D': ['B'], 'E': ['B', 'H'], 'F': ['C'], 'G': ['C'], 'H': ['E']} DFS遍历顺序（从A开始）: A B D E H C F G 已访问节点: {'A', 'B', 'D', 'E', 'H', 'C', 'F', 'G'}

关键点解析：

• visited集合至关重要，防止在图中形成无限循环（因为图可能有环）
• 递归调用时，系统自动使用调用栈来保存每层的状态
• 遍历顺序取决于邻居列表的顺序

3.2 二叉树的DFS遍历

二叉树的DFS有三种经典遍历方式，都是递归实现：

classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=val self.left=left self.right=right# 前序遍历：根 → 左 → 右defdfs_preorder(root):ifrootisNone:returnprint(root.val,end=' ')dfs_preorder(root.left)dfs_preorder(root.right)# 中序遍历：左 → 根 → 右defdfs_inorder(root):ifrootisNone:returndfs_inorder(root.left)print(root.val,end=' ')dfs_inorder(root.right)# 后序遍历：左 → 右 → 根defdfs_postorder(root):ifrootisNone:returndfs_postorder(root.left)dfs_postorder(root.right)print(root.val,end=' ')# 构建示例二叉树# 1# / \# 2 3# / \# 4 5root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)print("" + "="*50)print("【示例2】二叉树的DFS三种遍历方式")print("="*50)print("二叉树结构:")print(" 1")print("/\")print(" 2 3")print("/\")print(" 4 5")print(" 前序遍历（根-左-右）:",end=' ')dfs_preorder(root)print(" 中序遍历（左-根-右）:",end=' ')dfs_inorder(root)print(" 后序遍历（左-右-根）:",end=' ')dfs_postorder(root)

运行结果：

================================================== 【示例2】二叉树的DFS三种遍历方式 ================================================== 二叉树结构: 1 / 2 3 / 4 5 前序遍历（根-左-右）: 1 2 4 5 3 中序遍历（左-根-右）: 4 2 5 1 3 后序遍历（左-右-根）: 4 5 2 3 1

三种遍历的应用场景：

四、非递归实现DFS（显式栈）

递归实现虽然简洁，但当图/树很深时，可能导致递归栈溢出（RecursionError）。非递归实现使用显式栈来避免这个问题。

4.1 图的DFS非递归实现

fromcollectionsimportdequedefdfs_iterative(graph,start):visited=set()stack=[start]result=[]whilestack:node=stack.pop()ifnodenotinvisited:visited.add(node)result.append(node)print(node,end=' ')# 将邻居节点压入栈（反转顺序以保持与递归一致）forneighborinreversed(graph.get(node,[])):ifneighbornotinvisited:stack.append(neighbor)returnresultprint("" + "="*50)print("【示例3】图的DFS非递归遍历（显式栈）")print("="*50)print("DFS遍历顺序（从A开始）:")dfs_result=dfs_iterative(graph,'A')print(f" 遍历结果列表:{dfs_result}")

运行结果：

================================================== 【示例3】图的DFS非递归遍历（显式栈） ================================================== DFS遍历顺序（从A开始）: A B D E H C F G 遍历结果列表: ['A', 'B', 'D', 'E', 'H', 'C', 'F', 'G']

非递归实现关键点：

• 使用list的append()和pop()模拟栈操作
• 邻居节点需要反转顺序入栈，才能保证与递归实现遍历顺序一致
• 入栈时可以不检查是否已访问（出栈时检查），但入栈时检查效率更高

五、DFS经典实战：LeetCode 200. 岛屿数量

5.1 题目描述

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，计算岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

5.2 解题思路

这是DFS最经典的网格类应用：

1. 遍历每个格子，遇到’1’（未访问的陆地）就启动DFS
2. DFS将所有相连的’1’标记为’0’（"沉岛"策略）
3. 每启动一次DFS，岛屿数量+1

5.3 代码实现

defnumIslands(grid):ifnotgridornotgrid[0]:return0rows,cols=len(grid),len(grid[0])count=0defdfs(r,c):# 边界检查 + 水域检查（递归终止条件）ifr<0orr>=rowsorc<0orc>=colsorgrid[r][c]=='0':return# 标记当前陆地为已访问（沉岛策略）grid[r][c]='0'# 四个方向探索：上、下、左、右directions=[(-1,0),(1,0),(0,-1),(0,1)]fordr,dcindirections:dfs(r+dr,c+dc)# 遍历整个网格foriinrange(rows):forjinrange(cols):ifgrid[i][j]=='1':count+=1dfs(i,j)returncount# 测试用例grid1=[['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]print("" + "="*50)print("【示例4】LeetCode 200: 岛屿数量（DFS经典应用）")print("="*50)print("原始地图:")forrowingrid1:print(row)print(f" 岛屿数量:{numIslands(grid1)}")

运行结果：

================================================== 【示例4】LeetCode 200: 岛屿数量（DFS经典应用） ================================================== 原始地图: ['1', '1', '0', '0', '0'] ['1', '1', '0', '0', '0'] ['0', '0', '1', '0', '0'] ['0', '0', '0', '1', '1'] 岛屿数量: 3

DFS网格类问题模板总结：

defdfs_grid(grid,r,c):# 1. 边界检查ifnot(0<=r<len(grid)and0<=c<len(grid[0])):return# 2. 终止条件（根据题目调整）ifgrid[r][c]=='0':return# 3. 标记已访问grid[r][c]='0'# 4. 四个方向递归探索dfs_grid(grid,r-1,c)# 上dfs_grid(grid,r+1,c)# 下dfs_grid(grid,r,c-1)# 左dfs_grid(grid,r,c+1)# 右

六、DFS进阶：回溯与剪枝

6.1 什么是回溯？

回溯是DFS的一种特殊应用，用于搜索所有可能的解。当DFS走到死胡同时，"回溯"到上一步，尝试其他选择。

6.2 组合总和问题（带剪枝优化）

defcombination_sum(nums,target):result=[]nums.sort()defbacktrack(start,current_sum,path):# 剪枝：当前和已经超过target，无需继续ifcurrent_sum>target:return# 找到有效解ifcurrent_sum==target:result.append(path[:])returnforiinrange(start,len(nums)):# 去重剪枝：跳过重复元素ifi>startandnums[i]==nums[i-1]:continuepath.append(nums[i])backtrack(i,current_sum+nums[i],path)path.pop()# 回溯：撤销选择backtrack(0,0,[])returnresultprint("" + "="*50)print("【示例5】DFS回溯 + 剪枝优化")print("="*50)nums=[2,3,6,7]target=7print(f"数组:{nums}, 目标和:{target}")print(f"所有组合:{combination_sum(nums,target)}")

运行结果：

================================================== 【示例5】DFS回溯 + 剪枝优化 ================================================== 数组: [2, 3, 6, 7], 目标和: 7 所有组合: [[2, 2, 3], [7]]

回溯算法框架：

defbacktrack(路径,选择列表):if满足结束条件:result.add(路径)returnfor选择in选择列表:做选择 backtrack(路径,选择列表)撤销选择# 回溯

七、DFS常见陷阱与避坑指南

7.1 陷阱1：忘记标记已访问节点

# 错误示例：会导致无限循环！defdfs_wrong(graph,start):print(start,end=' ')forneighboringraph.get(start,[]):dfs_wrong(graph,neighbor)# 正确做法：始终维护visited集合defdfs_correct(graph,start,visited=None):ifvisitedisNone:visited=set()print(start,end=' ')visited.add(start)forneighboringraph.get(start,[]):ifneighbornotinvisited:dfs_correct(graph,neighbor,visited)

7.2 陷阱2：递归深度过大

importsys# Python默认递归深度限制为1000print(f"默认递归深度限制:{sys.getrecursionlimit()}")# 对于大规模数据，需要提高限制sys.setrecursionlimit(10000)# 更好的方案：使用非递归实现（显式栈）

7.3 陷阱3：网格DFS边界条件写错

# 错误：先标记再检查边界defdfs_bad(grid,r,c):grid[r][c]='0'dfs_bad(grid,r-1,c)# 正确：先检查边界，再标记defdfs_good(grid,r,c):ifr<0orr>=len(grid)orc<0orc>=len(grid[0])orgrid[r][c]=='0':returngrid[r][c]='0'dfs_good(grid,r-1,c)

八、DFS总结

8.1 核心要点

DFS 深度优先搜索 数据结构：栈（Stack）/ 递归调用栈 核心策略：纵向深入，不撞南墙不回头 关键操作：访问 -> 递归深入 -> 回溯 必备要素：visited集合（防循环） 时间复杂度：O(V + E) 空间复杂度：O(h)，h为最大深度

8.2 DFS适用场景