核心思想#

BFS 的核心是逐层扩展——从起始顶点出发，先访问其所有邻接顶点，再访问邻接顶点的邻接顶点，依此类推。过程类似于水波扩散。

• 数据结构：队列（FIFO），保证层次顺序
• visited 数组：标记已访问顶点，防止重复入队
• 每层距离相同：第 k 层的顶点距离源点恰好为 k

算法过程#

1
层次 0:  v0
2
层次 1:  v1  v2  v3      (v0 的邻接顶点)
3
层次 2:  v4  v5           (v1,v2,v3 的未访问邻接顶点)

1. 访问起始顶点 v，标记 visited[v] = true，v 入队
2. 队列非空时循环：队头 u 出队，检查 u 的所有邻接顶点 w，若 w 未访问则标记并入队
3. 队列为空时，从 v 出发可达的所有顶点均已访问

对于非连通图，需遍历所有顶点，对未访问的顶点再次调用 BFS（调用次数 = 连通分量个数）。

BFS 求无权图最短路径#

BFS 的一个关键应用是求无权图（边权均为 1）的单源最短路径。由于逐层扩展的特性，某顶点首次被访问时的距离一定是最短距离。

维护两个数组：

• d[v]：源点到 v 的最短距离（初始化为 -1 表示未访问）
• path[v]：v 的前驱顶点，用于回溯还原路径

路径还原：从目标顶点 t 沿 path[] 回溯到源点，逆序即为最短路径。

易错：BFS 求最短路径仅适用于无权图。如果边有不同的权值，BFS 的”最少边数”不等于”最小权值和”，此时必须使用 Dijkstra 算法。

BFS 生成树#

对连通图从 v 进行 BFS 时，所有引起顶点首次被访问的边构成一棵BFS 生成树。树中从根到任意顶点的路径即为原图中从 v 到该顶点的最短路径（边数最少）。非连通图对应BFS 生成森林。

核心思想#

DFS 的核心策略是尽可能深地搜索图的分支，走到死胡同时再回溯。

• 数据结构：栈（递归调用栈自动完成回溯）
• visited 数组：标记已访问顶点
• 回溯：当前顶点的所有邻接点都已访问时，沿原路退回上一顶点

算法过程#

1. 从起始顶点 v 出发，标记 v 为已访问
2. 依次检查 v 的所有邻接点 w：
   • 若 w 未被访问，递归地对 w 执行 DFS
   • 若 w 已被访问，跳过
3. 当 v 的所有邻接点都已被访问，回溯到上一层

非连通图：DFSTraverse 中调用 DFS 的次数 = 连通分量个数。

DFS 生成树#

对连通图进行 DFS，所有经过的边（递归调用时使用的边）构成一棵DFS 生成树。非连通图产生DFS 生成森林。

DFS 检测有向图环（三色标记法）#

DFS 可以用三种状态标记顶点来检测有向图是否有环：

• 0（未访问）：尚未遍历到
• 1（访问中）：在当前递归栈上
• 2（已完成）：该顶点的所有后继已遍历完毕

若 DFS 过程中遇到状态为 1 的顶点（即遇到了一条回边），则说明存在环。