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

一、什么是深度优先搜索DFS深度优先搜索Depth-First Search, DFS是一种用于遍历或搜索图、树的算法。其核心策略是从起始节点出发沿着一条路径尽可能深入地探索直到无法继续为止然后回溯到上一个节点继续探索其他分支。1.1 核心思想三步走深入从起始节点出发沿着一条路径一直走到尽头回溯遇到死胡同无未访问邻居时退回上一个节点重复继续探索其他分支直到所有节点都被访问1.2 形象比喻想象你在一个巨大的迷宫中探险你总是选择一条岔路一直走到底遇到死路就原路返回到上一个岔路口选择另一条没走过的岔路继续探索直到走遍迷宫的每一个角落这就是DFS的精髓——“不撞南墙不回头”。1.3 DFS遍历过程图解下面是一张DFS遍历过程的示意图展示了DFS如何沿着一条路径深入探索如上图所示DFS从节点A出发优先选择一条路径深入A → C → B走到尽头后回溯再探索其他分支C → D → F → G → E。二、DFS的数据结构支撑栈StackDFS的实现依赖于栈Stack这种数据结构。2.1 栈的特性栈是一种后进先出LIFO, Last In First Out的数据结构最后放入的元素最先被取出就像一摞盘子只能从最上面取放2.2 DFS与栈的关系DFS有两种实现方式都与栈有关实现方式栈的类型特点递归实现系统调用栈隐式代码简洁但有递归深度限制非递归实现手动维护栈显式避免栈溢出适合大规模数据三、递归实现DFS3.1 图的DFS遍历递归版# 图的DFS遍历 - 递归实现defdfs_recursive(graph,start,visitedNone):ifvisitedisNone:visitedset()# 访问当前节点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_nodesdfs_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,val0,leftNone,rightNone):self.valval self.leftleft self.rightright# 前序遍历根 → 左 → 右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 5rootTreeNode(1)root.leftTreeNode(2)root.rightTreeNode(3)root.left.leftTreeNode(4)root.left.rightTreeNode(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):visitedset()stack[start]result[]whilestack:nodestack.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_resultdfs_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’未访问的陆地就启动DFSDFS将所有相连的’1’标记为’0’沉岛策略每启动一次DFS岛屿数量15.3 代码实现defnumIslands(grid):ifnotgridornotgrid[0]:return0rows,colslen(grid),len(grid[0])count0defdfs(r,c):# 边界检查 水域检查递归终止条件ifr0orrrowsorc0orccolsorgrid[r][c]0:return# 标记当前陆地为已访问沉岛策略grid[r][c]0# 四个方向探索上、下、左、右directions[(-1,0),(1,0),(0,-1),(0,1)]fordr,dcindirections:dfs(rdr,cdc)# 遍历整个网格foriinrange(rows):forjinrange(cols):ifgrid[i][j]1:count1dfs(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] 岛屿数量: 3DFS网格类问题模板总结defdfs_grid(grid,r,c):# 1. 边界检查ifnot(0rlen(grid)and0clen(grid[0])):return# 2. 终止条件根据题目调整ifgrid[r][c]0:return# 3. 标记已访问grid[r][c]0# 4. 四个方向递归探索dfs_grid(grid,r-1,c)# 上dfs_grid(grid,r1,c)# 下dfs_grid(grid,r,c-1)# 左dfs_grid(grid,r,c1)# 右六、DFS进阶回溯与剪枝6.1 什么是回溯回溯是DFS的一种特殊应用用于搜索所有可能的解。当DFS走到死胡同时回溯到上一步尝试其他选择。6.2 组合总和问题带剪枝优化defcombination_sum(nums,target):result[]nums.sort()defbacktrack(start,current_sum,path):# 剪枝当前和已经超过target无需继续ifcurrent_sumtarget:return# 找到有效解ifcurrent_sumtarget:result.append(path[:])returnforiinrange(start,len(nums)):# 去重剪枝跳过重复元素ifistartandnums[i]nums[i-1]:continuepath.append(nums[i])backtrack(i,current_sumnums[i],path)path.pop()# 回溯撤销选择backtrack(0,0,[])returnresultprint( *50)print(【示例5】DFS回溯 剪枝优化)print(*50)nums[2,3,6,7]target7print(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,visitedNone):ifvisitedisNone:visitedset()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]0dfs_bad(grid,r-1,c)# 正确先检查边界再标记defdfs_good(grid,r,c):ifr0orrlen(grid)orc0orclen(grid[0])orgrid[r][c]0:returngrid[r][c]0dfs_good(grid,r-1,c)八、DFS总结8.1 核心要点DFS 深度优先搜索 数据结构栈Stack/ 递归调用栈 核心策略纵向深入不撞南墙不回头 关键操作访问 - 递归深入 - 回溯 必备要素visited集合防循环 时间复杂度O(V E) 空间复杂度O(h)h为最大深度8.2 DFS适用场景场景说明连通性检测岛屿数量、朋友圈、连通分量拓扑排序课程表、任务调度全排列/组合子集、排列、组合总和路径搜索迷宫问题找任意路径树遍历前序、中序、后序遍历