图DFS与BFS遍历算法

可视化演示

图的深度优先搜索(DFS)和广度优先搜索(BFS)是图算法的基础，分别基于栈和队列实现。本文讲解DFS的递归与... 切换模式查看不同维度。

DFS深度优先搜索

探险家背着一捆绳子和一盒粉笔进了迷宫。他的策略很“轴”：在每一个岔路口，用粉笔在走过的入口画个叉，然后永远优先选择没画叉的最深通道往前走。万一前方是死胡同，他就顺着绳子一步步退回上一个岔路口，再试下一条路。粉笔防止他重复走进同一条通道，绳子则代表“回溯”的依据——在代码里，这条绳子就是栈，而粉笔就是 visited 访问标记。

这段“走到底再回头”的过程，就是深度优先搜索（DFS）。给定一个起点顶点，DFS 沿着一条路径尽可能深地访问，直到这条路上没有未访问的邻居，再回溯到最近的分叉点继续。实现上，递归调用天然就是“栈”：函数调用栈帮你保存了每一层的回溯现场；你也可以用显式栈把递归改写成循环，原理完全一致——后进先出，后访问的邻居先被深入。

在无向图中，DFS 的递归式可以写成：访问当前顶点，再递归访问它的每一个未访问邻居。

所以 DFS 的“一根筋”性格来自递归 + 栈：一路深入，无路可退时把绳子收回来。面试和工程中，显式栈版本能避免递归过深导致栈溢出，但核心思想不变：能深入就深入，深入不了就回头。

BFS广度优先搜索

假设探险家换了一种策略：他不再自己走，而是在入口倒下一桶水，水波会同时朝所有方向漫延。第一圈的波纹覆盖所有紧挨着入口的岔路口，第二圈覆盖岔路口的岔路口……波纹扩散得越远，走过的步数越多。这种“一圈圈往外推”的方式，就是广度优先搜索（BFS）。

BFS 的核心是队列：先进先出（FIFO），保证先发现的顶点先被扩展。过程像流水线：从起点出发，把起点所有未访问邻居全部“入队”，然后一个一个出队，每出队一个顶点，又把它的未访问邻居继续入队。这样一来，第 1 层的顶点会在第 2 层之前全部出队处理，天然形成“逐层扫描”。

如果我们用 dist 数组记录“起点到每个顶点的层数”，那么当顶点 v 出队、首次发现邻居 w 时，w 的层数一定比 v 多 1：

BFS 的“水波”性格来自队列 + 逐层扩散：先见先处理，同层全部处理完才进入下一层。正因为如此，在无权图上，BFS 首次访问到某个顶点时，就一定走的是最短步数——水波最先到的，一定是最近的岸。

复杂度分析

探险队出发前要估算体力。走完整张图需要多少时间、多少背包空间，取决于你手里拿的是什么样的“地图”。邻接表像一张手绘通道清单：每个岔路口只记下直接相连的通道；邻接矩阵则像一张巨大的全景照片：所有点对之间“有无通道”都清清楚楚。

用邻接表存储时，DFS 和 BFS 的时间开销都很省：每个顶点被访问一次，每条边被检查一次（无向图中每条边会被两条邻接表记录各看一次，但常数倍可忽略），所以总时间是顶点数加边数。空间上，递归栈或队列在最坏情况下可能装下所有顶点。

如果换成邻接矩阵，检查一个顶点的所有邻居必须扫描一整行（V 个格子），所有顶点加起来就是 O(V²)。所以对稀疏图（边少），邻接表完胜；对稠密图，邻接矩阵的 O(V²) 也未必差——毕竟边数本身就有 V² 的量级。选哪种存储，就像选手绘清单还是全景照片，取决于迷宫的密度。

连通分量

地下迷宫往往不止一个洞窟：有些通道彼此相连成一片，但和另一片之间完全隔绝。在无向图中，这些“互不相通却内部连成一片”的顶点集团，就叫连通分量（Connected Component）。整个图被分成几块，就有几个连通分量。

怎么数清楚迷宫有几座“孤岛”？办法很简单：把所有顶点挨个询问一遍——如果某个顶点还没有被粉笔标记过，就说明它属于一座还没探索过的洞窟，于是从它启动一次 DFS 或 BFS，把这座洞窟里的所有顶点全部标记；计数加一。重复直到所有顶点都被标记过。

这个思想在图像处理里被称作洪水填充（Flood Fill）：从某个像素点出发，像倒水一样把颜色相同的连通区域全部染成新颜色——Photoshop 的魔棒工具就是这么识别一块区域的。对 AI 从业者来说，连通分量也是图聚类、社群发现最朴素的雏形：把社交网络分成互不交流的“朋友圈”，本质就是找连通分量。

环检测应用

迷宫里最怕遇到“回环通道”：你走了一圈，发现自己又回到了粉笔标记过的地方。在图中，这就是环（Cycle）。如果一张图里存在环，某些“依赖”关系就无法成立——比如课程 A 依赖 B，B 依赖 C，C 又依赖 A，那谁都没法先修。检测环，是拓扑排序和依赖解析的前提。

DFS 检测环有个优雅的“三色粉笔”技巧：白色表示完全没走过，灰色表示正在走但还没走完（还在当前探索栈中），黑色表示已经彻底探索完毕。当 DFS 在深入过程中碰到一条边，指向一个灰色顶点时，说明你绕了一圈回到了当前路径上的祖先——这就是环。

在 AI 工程中，环检测最常见的舞台是有向无环图（DAG）校验：机器学习流水线、任务调度框架（如 Airflow）都会先用 DFS 三色标记检查依赖图是否含环。一旦发现环，立刻报警，否则任务永远排不出执行顺序。

最短路径应用

水波搜索队最神奇的能力是：它天生知道最短路径。假定所有通道长度一样（无权图），我们从起点倒水，波纹到达某个岔路口的“圈数”，就是从起点到这个岔路口的最少步数。这个性质来自 BFS 的逐层扩散——第 k 层的顶点，最短距离恰好是 k。

算法上，我们用一个 dist 数组记录起点到每个顶点的距离，初始时起点为 0，其他顶点为无穷大。BFS 过程中，每当从队列中取出顶点 v、第一次发现邻居 w 时，就设置 dist[w] = dist[v] + 1。因为 BFS 保证顶点按层数从小到大出队，所以这个“第一次赋值”就是最短距离。

如果想还原整条路径，只需在设置 dist[w] 时顺手记下“前驱” prev[w] = v，最后从终点沿着 prev 一路回溯到起点，就得到完整路线。这在迷宫求解、电梯调度、社交“几度人脉”都是标准操作。注意：一旦通道有了不同长度（带权图），BFS 就不保证最短了，那要请出 Dijkstra 算法——那是后话。

遍历选型对比

现在你背包里有了两种工具：探险家的绳子（DFS）和水波的扩散桶（BFS）。干活前先想清楚任务类型。如果问题是“有没有一条路径通往宝藏”“打印所有可能的路线”“检测有没有回环”，DFS 更顺手——它可以快速深入解空间，配合回溯枚举所有情况。如果问题是“从入口到出口最少几步”，BFS 是唯一正确答案——它逐层扩散，第一次碰到出口时就是最短步数。

工程上还有个常被忽略的差异：空间占用。DFS 的空间和路径深度成正比，在树形分叉多的图上很省；BFS 的空间和“当前层最宽处”成正比，如果图是“扇形展开”，BFS 队列可能瞬间膨胀。另外 DFS 的递归实现代码极短，但递归太深有栈溢出风险，显式栈可以化解；BFS 用队列实现，逻辑直观，没有递归深度问题。

剪枝策略也常让选择改变：DFS 配合可行性剪枝，能在巨大的解空间里快速排除死路（比如八皇后、数独）；BFS 配合分支限界，则能在搜索树上按层剪掉次优分支。理解了 DFS 与 BFS 的底层性格，你就掌握了图算法世界的第一对“阴阳”。

AI 应用场景

Python 演示

from collections import deque def build_graph(edges):    graph = {}    for u, v in edges:        graph.setdefault(u, []).append(v)        graph.setdefault(v, []).append(u)    return graph def dfs_recursive(graph, start, visited=None, order=None):    if visited is None:        visited = set()        order = []    visited.add(start)    order.append(start)    for neighbor in graph.get(start, []):        if neighbor not in visited:            dfs_recursive(graph, neighbor, visited, order)    return order def dfs_stack(graph, start):    visited = set()    stack = [start]    order = []    while stack:        node = stack.pop()        if node in visited:            continue        visited.add(node)        order.append(node)        for neighbor in reversed(graph.get(node, [])):            if neighbor not in visited:                stack.append(neighbor)    return order def bfs_queue(graph, start):    visited = {start}    queue = deque([start])    order = []    while queue:        node = queue.popleft()        order.append(node)        for neighbor in graph.get(node, []):            if neighbor not in visited:                visited.add(neighbor)                queue.append(neighbor)    return order def count_components(graph):    visited = set()    count = 0    for node in graph:        if node not in visited:            dfs_recursive(graph, node, visited, [])            count += 1    return count def has_cycle(graph):    state = {}     def dfs(v):        state[v] = 1        for u in graph.get(v, []):            if u not in state:                if dfs(u):                    return True            elif state[u] == 1:                return True        state[v] = 2        return False     for v in graph:        if v not in state:            if dfs(v):                return True    return False if __name__ == "__main__":    edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)]    graph = build_graph(edges)    print("DFS recursive:", dfs_recursive(graph, 0))    print("DFS with stack:", dfs_stack(graph, 0))    print("BFS order:", bfs_queue(graph, 0))    print("components:", count_components(graph))    print("has cycle:", has_cycle(graph))

1. def build_graph(edges):把边列表转成邻接表，方便按顶点取邻居。
2. visited.add(start)相当于探险家在岔路口用粉笔画叉，防止重复进入。
3. for neighbor in graph.get(start, []):逐个取出当前顶点的邻居通道。
4. if neighbor not in visited:只走没被标记过的通道。
5. node = stack.pop()显式栈后进先出，模拟递归的“回溯现场”。
6. for neighbor in reversed(graph.get(node, [])):逆序入栈，让访问顺序与递归版一致。
7. queue = deque([start])队列初始化，起点先入队。
8. node = queue.popleft()从队头取出顶点，先进先出保证逐层扩散。
9. count += 1每启动一次完整遍历，就多一座“洞窟”（连通分量）。
10. state[v] = 1DFS 环检测中把顶点标记为灰色，表示正在递归栈中。

常见误区

面试题