1. 从迷宫到图论为什么我们需要DFS与BFS想象一下你站在一个巨大的迷宫里眼前是错综复杂的岔路。你的目标是找到出口。这时候你可能会采取两种截然不同的策略。第一种你选择一条路走到黑遇到死胡同就原路返回再尝试下一个岔路不放过任何一条可能的路径直到找到出口。第二种你站在起点先探索所有离你只有一步之遥的岔路口然后再探索从这些岔路口出发、两步能到达的地方像水波一样一圈圈扩散出去直到出口出现在你的“波前”上。这两种策略就是深度优先搜索DFS和广度优先搜索BFS最直观的体现。它们不仅仅是解决迷宫问题的工具更是计算机科学中遍历或搜索树、图这类数据结构的两大基石算法。无论是社交网络中寻找朋友关系链六度空间理论、编译器分析代码的语法树、游戏AI寻找最优路径还是网络爬虫抓取网页背后都离不开DFS和BFS的思想。很多初学者在刚接触这两个算法时容易被它们抽象的代码和术语吓到。但我想说它们的核心思想其实非常朴素就是我们人类在未知环境中探索时最自然的两种思维方式。今天我就用一个超级详细的、图示化的方式带你彻底搞懂DFS和BFS。我们不只讲代码怎么写更要讲清楚每一步“为什么”要这么做以及在实际写代码时那些教程里不会告诉你的“坑”在哪里。2. 深度优先搜索DFS一条道走到黑的“探险家”深度优先搜索顾名思义它的策略是尽可能深地搜索图的分支。当一条路走到尽头遇到死胡同或访问过的节点时它才会回溯Backtrack到上一个岔路口选择另一条未探索的路继续深入。这个过程很像我们玩密室逃脱或者走迷宫时执着于解开当前线索的策略。2.1 DFS的核心思想与递归实现DFS最自然的实现方式就是递归。递归函数完美契合了“深入”和“回溯”的过程。我们以一个简单的无向图为例目标是遍历图中所有节点。假设我们有以下图结构用邻接表表示这是最常用的表示方法之一特别适合稀疏图节点0: [1, 2] 节点1: [0, 3, 4] 节点2: [0, 5] 节点3: [1] 节点4: [1] 节点5: [2]我们的递归DFS函数伪代码思路如下访问当前节点比如打印节点值或进行其他操作。将当前节点标记为“已访问”防止重复访问形成死循环。对于当前节点的每一个“未访问”的邻居节点递归调用DFS函数。用Python代码实现看起来非常简洁def dfs_recursive(graph, node, visited): :param graph: 邻接表表示的图例如 {0: [1,2], 1:[0,3,4], ...} :param node: 当前访问的节点 :param visited: 集合用于记录已访问节点 if node in visited: return # 1. 处理当前节点 print(node, end ) # 2. 标记为已访问 visited.add(node) # 3. 递归访问所有未访问的邻居 for neighbor in graph.get(node, []): dfs_recursive(graph, neighbor, visited) # 初始化图和访问集合 graph {0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1], 5: [2]} visited set() print(DFS递归遍历结果: , end) dfs_recursive(graph, 0, visited) # 输出: DFS递归遍历结果: 0 1 3 4 2 5为什么递归能实现深度优先关键在于第3步的循环中的递归调用。函数在访问节点0后先遇到了邻居1它不会立即去访问节点0的另一个邻居2而是立刻“钻入”对节点1的递归中。在节点1的递归里它又会先“钻入”节点3然后是节点4。只有当节点1的所有邻居都处理完毕即递归调用全部返回控制权才会回到节点0的函数中这时才会去处理下一个邻居节点2。这个过程形成了一个“后进先出”LIFO的调用栈这正是深度的体现。2.2 DFS的迭代实现与显式栈递归虽然直观但在处理极深或规模极大的图时可能会引发栈溢出错误。因此掌握用迭代和显式栈Stack来实现DFS同样重要。这能让你更清晰地控制遍历过程。迭代DFS的步骤创建一个栈stack将起始节点压入栈。创建一个集合visited用于记录已访问节点。当栈不为空时循环 a. 弹出pop栈顶元素作为当前节点。 b. 如果该节点未被访问则处理它并标记为已访问。 c. 将该节点的所有未访问的邻居节点逆序压入栈中。逆序是为了和递归顺序保持一致但顺序不影响DFS的正确性只影响遍历序列。def dfs_iterative(graph, start): visited set() stack [start] # 使用列表模拟栈append入栈pop出栈默认弹出最后一个元素 while stack: node stack.pop() # 弹出栈顶 if node not in visited: print(node, end ) visited.add(node) # 将邻居逆序入栈以保证先入栈的后访问模拟递归的深度优先 # 例如节点0的邻居是[1,2]逆序后[2,1]入栈则先访问1再访问2 for neighbor in reversed(graph.get(node, [])): if neighbor not in visited: stack.append(neighbor) print(DFS迭代遍历结果: , end) dfs_iterative(graph, 0) # 输出: DFS迭代遍历结果: 0 1 3 4 2 5这里有一个极易踩坑的点标记访问的时机。注意看在迭代版本中我们是在节点从栈中弹出后才检查并标记访问。为什么不在入栈前标记因为同一个节点可能会被不同的邻居多次压入栈中。如果在入栈前标记那么后续其他邻居再尝试压入它时就会被跳过这虽然不会导致重复访问但可能会影响遍历的完整性在某些特定问题中。而在弹出后标记配合if node not in visited的判断可以确保每个节点只被处理一次。这是和BFS实现的一个关键区别BFS通常在入队前标记。2.3 DFS的典型应用场景与实战解析理解了DFS怎么走我们来看看它能干什么。DFS非常适合解决需要探索所有可能性的问题或者路径本身是解的一部分的问题。应用一查找路径问题比如经典的“3x3迷宫全0的DFS路径”问题。假设一个3x3网格0代表可通行1代表障碍。从(0,0)出发到(2,2)结束找出所有路径。DFS会递归地尝试上下左右四个方向每次尝试都是一条路走到黑走到死胡同或终点就回溯记录所有能到达终点的路径序列。这个“路径”就是指从起点到终点经过的坐标序列。应用二拓扑排序拓扑排序用于解决有向无环图DAG的任务调度问题比如课程选修的先后顺序。DFS可以实现拓扑排序对一个节点进行DFS在其所有后代节点都访问完成后再将该节点加入结果列表的头部。最终得到的结果列表就是一个合法的拓扑序。这是因为DFS保证了在输出一个节点时它的所有依赖子孙节点都已经输出完毕。应用三检测图中环在无向图中如果DFS过程中遇到了一个已访问过的节点并且这个节点不是当前节点的直接父节点在递归调用栈中的上一个节点那么就说明存在环。在有向图中环的检测需要引入“正在访问中”的状态比无向图稍复杂。应用四连通分量计数在非连通图中通过循环对每个未访问的节点调用DFS每一次完整的DFS调用就探索了一个连通分量。调用了几次DFS图就有几个连通分量。实操心得DFS的递归深度限制Python默认的递归深度限制在1000层左右。这意味着如果你的图深度超过1000比如一条长长的链递归DFS会抛出RecursionError。解决方法有两种1. 使用迭代DFS。2. 使用sys.setrecursionlimit()提高限制但这有风险可能导致C栈溢出和程序崩溃。对于未知深度的图迭代栈是更安全的选择。3. 广度优先搜索BFS层层递进的“指挥官”如果说DFS是执着深入的探险家那么BFS就是稳扎稳打的指挥官。它的策略是从起点开始先访问所有距离为1的邻居再访问所有距离为2的邻居依此类推。BFS找到的路径如果是无权图边没有权重那么一定是最短路径。3.1 BFS的核心思想与队列实现BFS必须使用队列Queue来实现这是由它“先进先出”FIFO的特性决定的。我们继续用之前的图为例。BFS的迭代步骤创建一个队列queue将起始节点入队。创建一个集合visited用于记录已访问节点。通常在这里就将起始节点标记为已访问。当队列不为空时循环 a. 出队dequeue队首元素作为当前节点。 b. 处理当前节点。 c. 将当前节点的所有未访问的邻居节点入队并立即标记为已访问。from collections import deque def bfs(graph, start): visited set([start]) # 起始节点入队前就标记 queue deque([start]) # 使用双端队列popleft出队append入队 while queue: node queue.popleft() # 弹出队首 print(node, end ) for neighbor in graph.get(node, []): if neighbor not in visited: visited.add(neighbor) # 入队前标记 queue.append(neighbor) print(BFS遍历结果: , end) bfs(graph, 0) # 输出: BFS遍历结果: 0 1 2 3 4 5为什么BFS要在入队前标记访问这是BFS与DFS迭代实现的一个关键区别。考虑节点A和节点B同时是节点C的邻居。在BFS中节点C出队后它的邻居A和B会被依次加入队列。如果不在入队时标记那么当节点A出队处理时它会尝试将邻居C再次入队因为C还未被标记这就会导致节点C被重复加入队列虽然最终因为visited检查不会重复处理但浪费了队列空间和计算时间在极端情况下可能导致队列爆炸式增长。因此BFS的标准写法是在节点入队时立即标记。3.2 BFS如何求解最短路径BFS最强大的应用之一就是求解无权图的最短路径。我们只需要在BFS的过程中额外记录每个节点距离起点的步数通常称为“层数”或“距离”。修改一下上面的BFS函数from collections import deque def bfs_shortest_path(graph, start): # 使用字典记录每个节点到起点的距离 distance {start: 0} queue deque([start]) while queue: node queue.popleft() current_dist distance[node] print(f节点 {node} 距离起点 {current_dist} 步) for neighbor in graph.get(node, []): if neighbor not in distance: # 如果邻居未被访问过即距离未知 distance[neighbor] current_dist 1 queue.append(neighbor) return distance graph {0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1], 5: [2]} dist bfs_shortest_path(graph, 0) print(各节点最短距离:, dist) # 输出: # 节点 0 距离起点 0 步 # 节点 1 距离起点 1 步 # 节点 2 距离起点 1 步 # 节点 3 距离起点 2 步 # 节点 4 距离起点 2 步 # 节点 5 距离起点 2 步 # 各节点最短距离: {0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 5: 2}为什么BFS找到的就是最短路径因为BFS是按“层”遍历的。距离起点为1的所有节点都在第一层被访问距离为2的在第二层被访问以此类推。当一个节点第一次被访问到时它所在的层数就是它到起点的最短距离。不可能有更短的路径因为如果有这个节点应该在更早的层就被访问到了。3.3 BFS的典型应用场景应用一社交网络中的“几度好友”在社交网络中你想知道另一个人是你的几度好友。把你的朋友看作一度好友朋友的朋友是二度好友。BFS从你开始第一层就是一度好友第二层就是二度好友以此类推。当目标人物出现在某一层时该层数就是你们的“距离”。应用二迷宫最短路径对于网格迷宫BFS是求解从起点到终点的最短步数的标准算法。每个网格是一个节点上下左右可移动的网格是邻居。BFS可以保证找到最短路径如果存在的话。网上很多“BFS迷宫C语言代码”就是解决这类问题。应用三网络爬虫的层级抓取搜索引擎的爬虫在抓取网页时从一个种子URL开始BFS地抓取其页面上的所有链接第一层然后再抓取这些链接页面上的新链接第二层这样可以系统地覆盖一个网站。应用四广播风暴与病毒传播模拟在计算机网络中广播包或病毒传播可以近似用BFS模型来模拟研究其传播速度和范围。避坑指南BFS中的状态去重在解决一些复杂状态搜索问题时比如八数码、华容道每个“状态”就是一个节点。BFS需要记录已访问过的状态防止重复进入循环。这时visited集合就不能只存一个ID了需要存整个状态的“快照”。对于复杂状态直接存储整个数据结构如二维列表效率低下且无法直接放入集合。常见的做法是将状态序列化为一个字符串如‘’.join(‘’.join(row) for row in board)或者计算一个哈希值如使用元组tuple(tuple(row) for row in board)作为键。这是BFS题目中非常关键的一步处理不好会导致内存溢出或超时。4. DFS vs BFS核心差异与选择策略学完了两种算法我们来做一次彻底的对比。选择DFS还是BFS往往取决于问题的性质和你想要的结果。特性深度优先搜索 (DFS)广度优先搜索 (BFS)数据结构栈 (Stack) - 递归调用栈或显式栈队列 (Queue)遍历顺序深度优先一条分支走到底再回溯广度优先一层一层向外扩展空间复杂度O(h)其中h是图的最大深度。对于树形结构空间优势明显。O(w)其中w是图的最大宽度。在最坏情况下完全图空间消耗巨大。时间复杂度O(VE)V是顶点数E是边数。两者在遍历整个图时是一样的。O(VE)与DFS相同。找到的路径不一定是最短路径。它找到的是某一条可行路径。在无权图中找到的从起点到目标点的路径是最短路径。适用场景拓扑排序、检测环、寻找连通分量、解决需要回溯的问题如八皇后、数独。最短路径问题、层级遍历、广播/传播问题、查找最近邻。实现复杂度递归实现极其简洁迭代实现需手动管理栈。通常只有迭代实现需手动管理队列和访问标记。如何选择问自己三个问题问题是否要求最短路径或最小步数如果是在无权图中首选BFS。图或树的深度是否可能非常大如果是递归DFS可能导致栈溢出应使用迭代DFS或BFS如果BFS宽度不大。是否需要遍历所有可能解如排列组合这类问题通常需要回溯DFS是天然的选择它的递归框架很容易实现回溯通过visited.remove(node)。一个常见的误解认为DFS一定比BFS快或省内存。这是错误的。在稠密图或者目标节点就在浅层时BFS可能更快找到解。而在深度很大但分支因子每个节点的子节点数很小的树中DFS的空间复杂度远低于BFS。性能取决于图的具体结构和问题的要求。5. 从理论到实战图解经典问题“二叉树的层序遍历”为了把BFS用活我们看一个LeetCode上的经典问题102. 二叉树的层序遍历。这个问题要求我们按层输出节点的值完美契合BFS的特性。问题描述给你一个二叉树返回其节点值的层序遍历。即逐层地从左到右访问所有节点。思路分析普通的BFS可以按顺序访问所有节点但它不区分层级。为了按层输出我们需要在BFS的过程中知道当前队列中的哪些节点属于同一层。技巧在于在每一轮循环开始时先记录当前队列的长度level_size这个长度就是当前层的节点数。然后只出队level_size次这些出队的节点就是当前层的所有节点将它们存入一个临时列表并将它们的子节点入队。循环结束后这个临时列表就是当前层的结果。图解过程假设我们有二叉树3 / \ 9 20 / \ 15 7初始化队列 [3] 结果列表 []。第一层当前队列长度 1。出队1次得到节点3。将3的值加入临时列表[3]。将3的子节点9和20入队。队列变为[9, 20]。将临时列表[3]加入结果列表结果 [[3]]。第二层当前队列长度 2。出队2次先得到节点9再得到节点20。临时列表变为[9, 20]。将9的子节点无和20的子节点15、7入队。队列变为[15, 7]。将[9, 20]加入结果结果 [[3], [9,20]]。第三层当前队列长度 2。出队2次得到节点15和7。临时列表为[15, 7]。它们都没有子节点。队列变空。将[15, 7]加入结果最终结果 [[3], [9,20], [15,7]]。代码实现from collections import deque # 假设二叉树节点定义 class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def levelOrder(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result这个“记录当前层大小”的技巧是BFS解决分层相关问题的核心模板务必掌握。6. 当DFS遇到回溯以“全排列”问题为例DFS在解决需要枚举所有可能性的问题时常常需要结合“回溯”算法。回溯的本质就是在递归调用DFS的每一层做出一个选择递归进入下一层当递归返回即到达“死胡同”或找到一个解时撤销当前层的选择回到上一层尝试其他选择。让我们以LeetCode46. 全排列为例。给定一个不含重复数字的数组nums返回其所有可能的全排列。思路分析我们可以把生成排列的过程想象成一棵决策树。第一层我们有n个选择选哪个数放在第一个位置。选定一个数后第二层我们在剩下的n-1个数中选一个放在第二个位置以此类推。DFS可以深入这棵树的每一个分支当一条分支到达叶子节点即排列长度等于n时我们就找到了一个解。然后我们需要回溯撤销最后的选择尝试同一层的其他选择。图解与代码def permute(nums): def backtrack(path, used): # 终止条件路径长度等于原数组长度说明一个排列完成 if len(path) len(nums): # 注意这里要添加path的副本因为path之后会被修改 result.append(path[:]) return # 遍历所有选择 for i in range(len(nums)): if not used[i]: # 如果数字nums[i]没有被使用过 # 做选择将数字加入路径并标记为已使用 path.append(nums[i]) used[i] True # 递归进入下一层决策树 backtrack(path, used) # 撤销选择回溯的关键步骤 path.pop() used[i] False result [] # used数组用于标记nums中每个元素是否已被使用 used [False] * len(nums) backtrack([], used) return result # 测试 print(permute([1, 2, 3])) # 输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]回溯的三要素路径path已经做出的选择。选择列表nums中未使用的部分当前可以做的选择。结束条件到达决策树底层无法再做选择这里指路径长度等于数组长度。为什么需要path[:]在Python中list是可变对象。result.append(path)添加的是path列表的引用而不是其当前状态的快照。后续path.pop()操作会修改这个列表导致result中已经添加的排列也被修改。path[:]创建了path的一个浅拷贝副本冻结了当前的状态。经验之谈DFS回溯的调试技巧回溯算法的递归树往往很深直接看结果出错很难定位。一个有效的调试方法是打印递归的“轨迹”。在backtrack函数的开头和“撤销选择”后添加打印语句输出当前的path和used状态。这能帮你清晰地看到程序是如何一步步探索和回溯的。对于复杂回溯问题先在纸上画决策树再对应代码是最高效的学习方法。7. 进阶挑战在二维网格中运用DFS/BFS很多面试题和竞赛题都喜欢在二维网格比如迷宫、岛屿、棋盘上考察DFS/BFS。这类问题有一个通用技巧方向数组。假设网格是m x n的每个格子有上下左右四个邻居。我们可以定义一个方向数组# 四个方向上右下左 directions [(-1, 0), (0, 1), (1, 0), (0, -1)] # 如果是八连通包括对角线则可以定义八个方向 # directions [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]例题200. 岛屿数量给你一个由1陆地和0水组成的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。解题思路DFS版本遍历整个网格。当遇到一个1陆地时岛屿数量加1。然后从这个1开始进行DFS或BFS将所有与之相连的1都标记为已访问比如改成0或一个特殊标记这样一整块岛屿就被“淹没”或“标记”了。继续遍历重复步骤2-3。def numIslands(grid): if not grid: return 0 m, n len(grid), len(grid[0]) count 0 directions [(-1,0), (1,0), (0,-1), (0,1)] def dfs(i, j): # 将当前陆地标记为‘0’水表示已访问 grid[i][j] 0 # 遍历四个方向 for di, dj in directions: ni, nj i di, j dj # 如果新坐标在网格内且是陆地则继续DFS if 0 ni m and 0 nj n and grid[ni][nj] 1: dfs(ni, nj) for i in range(m): for j in range(n): if grid[i][j] 1: count 1 dfs(i, j) # 淹没整个岛屿 return count为什么选择DFS这个问题不关心路径长度只关心连通块的数量。DFS的递归实现非常简洁能很好地完成“标记整个连通区域”的任务。当然用BFS也一样可以。网格DFS/BFS的注意事项边界检查在访问(ni, nj)前必须检查0 ni m and 0 nj n防止数组越界。访问标记必须修改原网格或使用单独的visited矩阵防止重复访问陷入无限循环。修改原网格通常更节省空间。方向数组使用方向数组能让代码更清晰避免写四行重复的if判断。8. 总结与更高阶的思考通过上面这些详细的图示和代码拆解相信你已经对DFS和BFS有了从思想到实现的全面理解。它们看似简单却是构建更复杂算法如Dijkstra最短路径算法、A*搜索算法的基础。在实际工程和面试中纯粹的DFS/BFS模板题越来越少更多的是它们的变体和组合。例如双向BFS从起点和终点同时开始BFS当两个搜索相遇时停止。用于优化大规模图的最短路径搜索。启发式搜索A*在BFS的基础上引入一个评估函数启发函数来优先探索更有可能接近目标的节点。迭代加深搜索IDS结合了DFS空间效率高和BFS能找到最短路径的优点。它按深度限制进行DFS逐渐增加深度限制直到找到解。最后我的个人体会是学习算法不能停留在背诵模板。一定要动手画图模拟算法的执行过程理解每一个数据结构的角色栈、队列、集合理解每行代码背后的意图。当你能清晰地解释为什么BFS要在入队时标记访问而DFS迭代可以在出栈时标记当你能在面对新问题时自信地判断该用DFS还是BFS时你才算真正掌握了它们。下次当你再看到“DFS迷宫路径”或“BFS最短步数”时希望你的脑海里能立刻浮现出它们运行的生动画面。