企业官网建设流程全解析

很多人第一次学图遍历的时候，都会觉得DFS和BFS不过就是两个模板，背下来就完事。但真到了做题或者处理实际图数据的时候，经常会卡在一个问题上：这题到底该用DFS还是BFS？或者更尴尬的是，用DFS写出了答案，结果超时；换成BFS，又不知道状态该怎么组织。这个系列我会从图的遍历开始，把图论算法里最基础也最影响后续理解的几个点掰开揉碎。第一篇先讲DFS和BFS，重点不是贴两段能跑的代码，而是把两者的遍历顺序差异、数据结构选择、以及在什么场景下选哪一种，讲清楚。

如果你正准备应付算法面试、刷LeetCode图论题，或者需要处理真实业务里的依赖关系、网络连通性、路径规划问题，这篇内容应该能帮你省下不少摸索时间。前面先说结论，后面每一节都会展开：DFS是沿着一条路走到黑，走不通再回头，天然擅长探索和回溯；BFS是一层一层往外扩，天然擅长找最短路径。这个差异决定了它们各自能解决什么样的问题，也决定了它们的代码结构和踩坑点完全不同。

1. 先想清楚：DFS和BFS的根本差异在哪

很多教材上来就扔出两段代码，然后告诉你一个是栈，一个是队列。这当然没错，但光记住这个结论远远不够。你得先理解，为什么DFS要用栈而BFS要用队列，这个选择不是随便定的，它直接来自两种搜索策略的遍历顺序。

DFS的遍历顺序是“能往前就往前”。从起点出发，随便挑一个邻居走进去，然后继续挑这个邻居的邻居，一直深入到不能再深入为止，再回溯到上一个岔路口，选另一条没走过的路。这种后进先出的行为，恰恰和栈的特性完全一致。你用递归实现DFS的时候，其实是操作系统帮你维护了一个隐式栈，每次递归调用就把当前函数的状态压栈，返回的时候再弹出来。这个状态里保存的是当前节点、已经访问到第几个邻居等信息，保证你回溯到上一层时，还能接着之前的位置继续。

BFS的遍历顺序刚好反过来，是“一层一层扫”。从起点出发，先把所有和起点直接相连的节点都访问一遍，然后再去访问这些节点的邻居，也就是距离起点两步的节点，再然后是三步、四步。这种先进先出的行为，就是队列的天然用法。先进入队列的节点先被处理，保证距离起点更近的节点永远比更远的节点先被扩展。

你可以把DFS类比成在迷宫里走路的探索者，他手里只有一根绳子，每到一个岔路口就选一条路走，走不通了顺着绳子退回上一个岔路口再换方向。BFS则像是往水里扔了一块石头，波纹一圈一圈往外扩散，每一圈波纹就是距离起点相同步数的节点集合。

这个顺序上的差异，直接决定了DFS和BFS在面对同一张图时的行为模式完全不同：

理解到这个层面，你在选型的时候就不会再纠结“是不是DFS快一点”或者“BFS是不是更稳”，而是直接问自己：我关心的是“能不能到达”还是“最短几步到达”？关心前者，DFS通常更直接；关心后者，BFS基本是唯一选择。下一节先把图的存储方式说清楚，因为很多人的问题不是出在搜索算法本身，而是图存得不对，导致后续所有遍历逻辑都跟着变扭。

2. 图怎么存：邻接矩阵和邻接表的选型逻辑

DFS和BFS都得建立在“图已经存在程序里”这个前提上。图的存储方式直接影响遍历时访问邻居的效率，也影响整个算法的复杂度。最常用的两种方式是邻接矩阵和邻接表，很多人默认用邻接矩阵，因为写起来简单，一个二维数组搞定。但真到了处理大规模图的时候，邻接矩阵往往会成为性能瓶颈。

邻接矩阵就是用graph[i][j]来表示顶点 i 和顶点 j 之间是否有边。如果是有权图，就存边的权值。这种存储方式有几个特点：判断两个顶点是否相连只需要 O(1) 时间，非常快；但存储空间是 O(V²)，V 是顶点数。当顶点数很多、边很少（也就是稀疏图）的时候，这个矩阵里大部分位置都是空的，空间浪费非常严重。比如 10000 个顶点，开一个二维数组就是 1 亿个元素，不管边有多少，光初始化这个数组就要不少时间。

邻接表则是为每个顶点维护一个列表，列表里存的是这个顶点能直接到达的邻居。在 Python 里通常用一个列表的列表，或者字典加列表的形式。邻接表只存存在的边，空间复杂度是 O(V+E)，E 是边数，适合稀疏图。遍历一个顶点的所有邻居，复杂度就是该顶点的度数，整体遍历全图的时间是 O(V+E)。

选邻接矩阵还是邻接表，主要看两个因素：顶点数量和图的稠密程度。如果顶点数在几百这个量级，而且你需要频繁判断两个点之间是否有边，邻接矩阵会非常方便。如果顶点数上千甚至更多，或者图是稀疏的，邻接表是更合理的选择。实际刷题和业务里，绝大多数图都是稀疏图，所以邻接表用得更多。

还有一个细节很多人都踩过坑：无向图在邻接表里存的其实是两条有向边。比如 1 和 2 之间有边，那么 1 的邻居列表里有 2，2 的队列列表里也有 1。如果你只加了一条，遍历的时候就会发现有些节点明明相连却访问不到，这就是典型的“边只加了一半”。我个人习惯在写建图函数时统一封装一个add_edge，无向图就在函数里同时加两条，避免每次手写都漏。

from collections import defaultdict # 邻接表：每个顶点对应一个邻居列表 graph = defaultdict(list) def add_undirected_edge(u, v): graph[u].append(v) graph[v].append(u) def add_directed_edge(u, v): graph[u].append(v)

这个建图代码虽然简单，但却是后面所有遍历代码的基础。如果你的图数据是带权重的，邻接表里的元素就可以从一个数值变成一个二元组(邻居, 权值)，遍历的时候再解包即可。确认存储方式没问题之后，下面两节分别把 DFS 和 BFS 的两种实现、以及它们真正容易出错的地方讲透。很多人会在这两个算法上写出“能过样例但实际是错的”的代码，就是因为对访问标记的时机理解不到位。

3. DFS的本质：一条路走到黑背后的系统栈与回溯

DFS 的实现通常有两种形式：递归和显式栈。递归代码看着简洁，但隐藏了很多操作系统帮你做的栈操作；显式栈则需要你自己管理状态，代码长一些，好处是不容易爆栈，而且遍历顺序更可控。两种方式我都建议掌握，因为它们各自能解决不同的问题。

3.1 递归写法与访问标记的时机

递归实现的核心逻辑是：从当前节点出发，标记已访问，然后依次对所有邻居做递归调用，前提是邻居未被访问。

visited = set() def dfs(node): if node in visited: return visited.add(node) # 这里可以对 node 做处理，比如记录路径、输出节点 for neighbor in graph[node]: dfs(neighbor) # 遍历全图所有连通分量 for node in graph: if node not in visited: dfs(node)

这段代码看起来很简单，但有一个至关重要的细节：visited.add(node)到底放在哪里。上面的写法是在进入节点时立刻标记。如果你不小心把标记放在递归返回之后，也就是整个子树都处理完了再标记，那就会导致同一层多个邻居之间互相重复调用，甚至进入死循环。

这里值得多说一句“访问标记的时机”和“回溯的撤销”之间的关系。上面这种遍历方式，一旦一个节点被访问过，它在整个DFS过程中都不会再被访问，适用于连通性检测、连通分量划分这类问题。但如果你要做的不是“遍历整张图”而是“找到所有从起点到终点的路径”，那你就需要在一路深挖的过程中保存当前的路径，并在递归返回时撤销选择。这就是经典的回溯，DFS和回溯在代码形式上很接近，但解决的问题完全不同。

def dfs_all_paths(node, target, path, result): if node == target: result.append(path.copy()) return for neighbor in graph[node]: if neighbor not in path: # 不重复经过当前路径上的节点 path.append(neighbor) dfs_all_paths(neighbor, target, path, result) path.pop() # 回溯：撤销选择

回溯的关键就在path.pop()这一行。没有这一步，路径列表就会一直累积错误的节点。你从u递归进入v，等v的所有子树都处理完，回到u继续处理其他邻居时，必须把v从路径里拿出来，否则其他邻居的路径里会莫名其妙带着v。我用一个不太恰当的比喻：递归进入下一步就相当于在路径上再铺一块砖，而回溯则是把多余的砖头撤掉，保证无论走到哪一步，路径记录的都恰好是当前这条分支上的节点。初次接触DFS的人，建议在纸上手动模拟三层递归的压栈和弹栈过程，才能真正理解为什么“撤一步”能换来“所有路径”的正确性。

3.2 非递归写法：显式栈的几个坑

递归虽然简洁，但在图深度很大的时候，会遇到递归深度限制的问题。语言自带的调用栈是有限的，递归层数几千层之后就可能直接栈溢出或程序崩溃。这时候要改成显式栈，自己维护一个栈容器来模拟递归的过程。

stack = [start] visited = set([start]) while stack: node = stack.pop() # 对 node 做处理 for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) stack.append(neighbor)

这里有个非常容易被忽略的差异：显式栈的访问顺序和递归不一定是完全一致的。原因在于，递归是“遇到一个未访问的邻居立刻深入”，而显式栈是把所有未访问邻居一股脑压入栈里，下一次弹出的位置取决于栈顶，也就是最后压入的邻居。所以，如果你需要DFS按特定顺序遍历，比如优先走编号小的邻居，那就得在压栈前对邻居排序。这个和BFS的“层级顺序”完全无关，但它决定了显式栈版本的代码在输出遍历序列时，和递归版本可能不同。很多初学者用两种写法跑同一个用例，发现输出顺序不一样，就怀疑程序有bug，其实这是正常现象。

显式栈还有一个常见坑：入栈时机。上面的代码是在“入栈时”就标记 visited，而不是在“出栈时”标记。为什么不能出栈时标记？因为如果没有在入栈时拦截，那同一个节点可能会被多个不同的父节点重复压入栈。比如节点 A 同时是 B 和 C 的邻居，B 和 C 都已经在栈里了，等到处理 B 时，发现 A 还没访问过，就压入 A；再处理 C 时，又发现 A 还没访问过，又压入一个 A。这样栈里会出现多个相同的节点，不仅处理冗余，在最坏情况下会指数级爆炸。入栈时标记，相当于把“是否已访问”的判断提前，确保每个节点只入栈一次。

非递归DFS通常还要手动记录额外的状态，比如“当前处理到了第几个邻居”，否则你很难模拟递归回溯到上一层后“接着上次的位置继续”的效果。这也是为什么很多场景下，递归写法虽然可能爆栈，却依然被广泛使用的原因——它帮你隐式保存了太多过程信息。

3.3 DFS在哪些问题里是首选

DFS天然适合这些问题：求解图的连通分量、判断两个点是否连通、检测图中是否存在环、做拓扑排序（用DFS的方式，在递归返回时记录节点）、以及所有“枚举路径/方案”类的问题。这类问题的共同点是，它们不太关心“最短”这两个字，更关心“有没有”或者“有多少”。

就拿连通分量来说，不管图多大，你只需要从任意未访问节点出发做一次DFS，把所有能走到的节点都标记上，这就形成一个连通分量。然后换一个未访问节点继续，最后数一数启动了几次DFS，就是连通分量的个数。这个过程用BFS也能做，但DFS在代码写作上通常更简洁，尤其递归版本，几乎就是照着定义写。

4. BFS的本质：逐层扩散背后的队列与最短路径

如果你要解决的问题是“从起点到目标点，最少要经过多少步”，那么DFS基本帮不上忙，因为DFS找到的第一条路径通常只是“一条路”，不能保证它最短。这时候BFS才是正解。BFS之所以能保证无权图最短路径，是因为它严格按“距离起点越近越先被访问”的顺序扩展节点。

4.1 队列实现与层次信息

BFS用队列实现，核心逻辑是：初始时把起点放入队列，记录起点层次为0；每次从队列头部取出一个节点，处理它；然后把所有未访问的邻居放入队列尾部，这些邻居的层次是当前节点层次加1。

from collections import deque def bfs(start, target): queue = deque([start]) visited = {start} distance = {start: 0} while queue: node = queue.popleft() if node == target: return distance[node] for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) distance[neighbor] = distance[node] + 1 queue.append(neighbor) return -1 # 不可达

为什么这个代码返回的步数一定是最短步数？关键在于 BFS 的逐层扩展特性。端点先入队的节点一定先出队，而入队的顺序又是严格按层次从小到大排列。假设起点可以直达的所有节点层次都是1，这些节点全部入队后，队列尾部才开始加入层次为2的节点。由于队列先进先出，所有层次为1的节点一定比层次为2的节点先被取出。以此类推，当某个目标节点第一次被从队列中取出时，它一定处于所有可能访问情况下最早的那一层，所以对应的步数就是最短步数。

这里有个很实用的变体：如果题目要求记录最短路径的具体节点序列，而不只是步数，那就在BFS过程中维护一个prev字典，记录每个节点是从哪个节点过来的，最后从目标节点逆推回起点，再反转即可。因为BFS保证每个节点第一次被访问时对应的路径就是最短路径，所以这个prev关系直接可以用。

4.2 最容易被忽视的细节：visited标记的时机

我在前面DFS显式栈那一节强调过“入栈时标记”，在BFS里同样有对应的问题，而且这个坑更隐蔽。请看下面这段错的代码：

queue = deque([start]) visited = set() while queue: node = queue.popleft() if node in visited: continue visited.add(node) for neighbor in graph[node]: if neighbor not in visited: queue.append(neighbor)

这段代码看起来好像也没问题，但注意visited.add(node)是放在出队时才执行的。问题在于，一个节点可能在被取出之前，就已经被多个不同父节点添加进队列了。比如节点 A 是 B 和 C 的共同邻居，B 先入队，C 后入队。处理 B 时把 A 入队，A 还没被访问；处理 C 时又发现 A 不在 visited 里，于是又入队一个 A。这样队列里就有两个 A，后面取出第一个 A 会处理一次，取出第二个 A 时虽然被continue跳过，但白白浪费了一次出队操作。在极端情况下，比如网格图、环形结构，这种重复入队会呈指数增长，导致程序直接超时。

正确的做法是在入队时立即标记 visited。也就是上面第一段BFS代码里的写法：visited.add(neighbor)在queue.append(neighbor)之前或同时执行。这样当第二个父节点试图入队 A 时，发现 A 已经在 visited 里，就不会再次入队。这个细节，初学者十有八九会踩到。如果是自己练习时发现BFS莫名其妙超时，先检查是不是 visited 标记时机写错了。

4.3 BFS的扩展形态与适用场景

BFS不止能解决无权图最短路，它还有一些很实用的变体。多源BFS就是其中一个典型应用。假设题目给的图里有很多个源点，想求每个点到最近源点的距离，这时候不需要对每个源点各做一次BFS，而是把所有源点同时放入初始队列，按普通BFS跑一次就行。因为所有源点处于第0层，它们的邻居都属于第1层，依次扩散，就能一次性算出每个点到最近源点的距离。LeetCode上经典的“01矩阵”就是这种思路。

还有“0-1 BFS”，专门处理边权只有0和1的图。它用双端队列替代普通队列，遇到权值为0的边就把邻居从队头插入，权值为1的边就从队尾插入。这样能保持队列内距离的单调性，把最短路径问题的复杂度控制在 O(V+E)，比通用Dijkstra算法更简洁。不过这个属于进阶内容，这里先留个印象，后面文章会单独展开。

BFS的核心适用范围是：无权图最短路径、最少步数类问题、层级遍历、多源扩散问题、以及某些状态的按层展开。判断一个题能不能用BFS，你就看它是不是在“求最小值，而且是按层扩散的模型”。

5. 从模板到实战：五类高频问题的选型逻辑

光记住两个模板，离真正做题还有一段距离。实际刷题的时候，你面对的是一个具体的题目描述，它不会告诉你“请用BFS”，你需要自己判断。总结一下我刷题过程中最常见的几类问题，以及它们的选型套路。

5.1 连通性检测与连通分量（DFS/BFS皆可）

这类问题的典型表现是：给定一个二维网格的陆地和水域，问有多少个岛屿；或者给定社交网络关系，问有多少个互不相连的圈子。核心是“从任意未访问节点出发，遍历整个连通块”。这种题用DFS和BFS都能做，代码差别不大。我通常选DFS，因为递归写法更短。但如果你担心递归爆栈，就改用BFS或显式栈。

以LeetCode 200“岛屿数量”为例，思路是遍历整个网格，每遇到一个未访问过的陆地块，就计数加一，然后从这个格子出发，把整个连通的陆地都标记为已访问。DFS版核心逻辑就几行：

def dfs(grid, r, c): if not (0 <= r < len(grid) and 0 <= c < len(grid[0])): return if grid[r][c] != '1': return grid[r][c] = '0' # 直接把访问过的陆地改成水域，相当于 visited dfs(grid, r+1, c) dfs(grid, r-1, c) dfs(grid, r, c+1) dfs(grid, r, c-1)

这里有个很聪明的技巧：用修改原数组的方式替代 visited 数组，把访问过的陆地改成 '0'，省空间还省事。这个技巧在很多网格类DFS题里都适用，前提是你允许修改输入数据。

5.2 无权图最短路径（BFS首选）

题目描述里只要出现“最少几步”“最短路径”“最少经过几站”这些字眼，且图上没有权重或权重相同，优先上BFS。比如迷宫寻路的最少步数、单词接龙的最少转换次数、公交线路的最少换乘次数。这些题的本质都是在图上做BFS，只是图的结构可能藏在题目里，需要你先显式或隐式地把图建出来。

“隐式建图”这个点特别值得留意。很多最短路径题目不会直接给你一个漂亮的邻接表，而是给你一个网格、一个字符串集合，甚至一个状态空间。但只要你把“从一个状态能转移到哪些状态”搞清楚，BFS的模板几乎可以直接套用。以单词接龙为例，每个单词是一个节点，两个单词之间如果只有一个字母不同就有边。虽然你可以先暴力建图再跑BFS，但更高效的做法是在BFS过程中实时生成邻居，也就是枚举每个位置尝试替换成其他字母，再看是否在单词集合里。这样做的好处是避免了 O(n²) 的建图开销。

5.3 枚举所有路径与方案（DFS+回溯）

当题目要求“找出所有可行的方案”“返回所有路径”“枚举所有排列组合”时，DFS加回溯几乎是固定解法。比如LeetCode 797“所有可能的路径”，给定一个有向无环图，求从节点0到节点n-1的所有路径。这种题用BFS也能做，但状态管理会非常麻烦，因为BFS按层扩散，不同路径会共享很多状态，你需要在每个节点保存从起点到当前节点整条路径的快照，内存浪费很大。DFS的回溯机制天然把路径信息放在递归栈里，写起来顺手得多。

回溯里的剪枝也是一门大学问。简单说就是提前判断某些分支不可能产生可行解，直接跳过。比如在迷宫类问题里，如果当前方向越界或撞墙就直接返回不再深入。剪枝之所以重要，是因为DFS如果不剪枝，复杂度会随分支数指数增长，而剪枝往往能把大量无效分支提前砍掉，让程序在可接受时间内跑完。

5.4 拓扑排序（DFS或BFS各有对应）

拓扑排序是对有向无环图的一种线性排序，要求每个节点在它所有后继节点之前出现。它有两种实现方式：Kahn算法用BFS思路，不断找出入度为0的节点并移除；DFS版则是在递归返回时把节点加入结果，最后反转。两者都能做，但Kahn算法的入度计数方式更直观，而且可以顺带检测图里是否有环（如果最终排序结果节点数不等于总节点数，说明有环）。

DFS版拓扑排序对于理解“DFS的结束顺序”很有帮助，但面试时我一般默认用Kahn算法，因为它不容易在递归边界上出错。这个内容涉及的知识点较多，以后单独写一篇拓扑排序专题时再展开，这里只提示一点：你看到“先决条件”“依赖关系”“课程安排”这些词，就应该联想到拓扑排序。

5.5 二分图判定（BFS/DFS染色法）

二分图判定问题用DFS或BFS都能做，核心是给每个节点染色，要求相邻节点颜色不同。DFS写法简单，从起点开始染色，递归访问邻居时染相反颜色，如果遇到已经染色且颜色相同的邻居，就说明不是二分图。BFS版本只是把递归换成队列，逻辑完全一样。

这类题的价值在于，它强迫你理解“图遍历不只是走一遍，还能在遍历过程中携带额外信息”。DFS/BFS里除了把节点标记为已访问，还可以存储颜色、距离、状态等附加信息。掌握这个思路以后，很多看似复杂的图论问题都会变得容易下手。

6. 从跑通到跑稳：栈溢出、剪枝与双向BFS的进阶问题

看到这里，你应该能从算法模板和经典题型两个层面判断DFS和BFS的选型了。但真正实战中，还需要解决一些让程序从“能跑”变成“跑得稳”的问题。我最后把这些年踩过的几个高频坑集中说一下。

第一个是递归深度限制。Python 的默认递归深度大约在 1000 层左右，如果你的图是一条长链，DFS递归深度可能直接超过这个限制，程序抛RecursionError直接崩掉。两种解决思路：一是调用sys.setrecursionlimit(10**6)把递归深度上限调大，这个方法简单但有时候只是拖延问题，因为操作系统本身的调用栈资源也是有限的；二是干脆用显式栈写非递归DFS，彻底绕开递归深度问题。我建议在刷题做练习时两个版本都写一遍，理解它们各自的特点，实际应用时根据场景弹性选择。

第二个是DFS的剪枝优化。很多初学者以为DFS不超时的关键就是剪枝，这话对了一半。剪枝确实非常重要，但更重要的是先想清楚状态的表示方式。同一个问题，状态如果设计得好，分支数量会急剧减少。比如在某些矩阵路径问题里，如果把“已访问状态”用一个位掩码存在一个整型变量里，会比用一个集合快很多。状态设计这件事和具体题目强相关，没法一概而论，但有一个通用原则：尽量避免重复计算相同的子状态，一旦发现相同状态会被反复访问，优先考虑记忆化搜索。

第三个是双向BFS。当起点和终点都明确，且图规模很大时，单向BFS可能扩展出巨量节点。比如一个分支因子为 b 的图，搜 k 层会扩展出大约 b^k 个节点；双向BFS从起点和终点同时开始各搜 k/2 层，两边加起来大约 2*b^(k/2) 个节点，差距非常明显。双向BFS的实现并不复杂，维护两个队列、两个 visited 集合，每次扩展节点更少的那一侧，一旦某个节点同时被两侧访问到，就说明找到了最短路径。LeetCode的“单词接龙 II”这类题，用双向BFS能明显感受到性能提升。

第四个是BFS在网格图中的方向处理。网格图里常见的四方向移动，很多人在写方向数组时用四个if分别判断上下左右，代码丑不说，还容易漏情况。通常建议用两个数组directions = [(-1,0), (1,0), (0,-1), (0,1)]循环处理，这样代码简洁，也方便扩展到八方向问题。

第五个，也是我特别想提醒的一点：图的遍历算法不只是竞赛或面试的工具。在业务系统里，判断用户权限组之间的继承关系、分析服务依赖链上的环、计算供应链网络中的最短路径，这些都要用到DFS和BFS的基本思想。你把这个基础打牢，后面学Dijkstra、拓扑排序、Tarjan算法、网络流都会顺畅很多。

写在最后的话，可能听起来有点陈旧，但确实是经验之谈：学图遍历，不要只看代码，一定要在纸上或者白板上手动推演一遍。我自己当年学DFS，就是画了一张包含环的无向图，然后手动模拟栈的每一步变化，才真正理解了为什么访问标记要放在入栈时而不是出栈时。如果你能独立把这个过程推演清楚，DFS和BFS就不再是两个需要背诵的模板，而是你工具箱里随时能拿出来用的趁手工具。这次先写到这里，下一篇计划聊图论算法的下一个基础概念，到时候再接着往里挖。