13.4.3 图的遍历

图没有根和左右子树，所以不能使用二叉树的先序、中序、后序。图遍历的核心是：从某个顶点出发，沿边访问可达顶点，每个顶点访问一次。常见方式是深度优先和广度优先。

深度优先 DFS

DFS 的策略是“一条路走到底，走不通再回退”。它类似树的先序递归，也可以用栈实现。

flowchart TD
  A["访问当前顶点"] --> B["找第一个未访问邻接点"]
  B --> C{"找到了？"}
  C -->|是| D["进入该邻接点，继续 DFS"]
  D --> B
  C -->|否| E["回退到上一层"]

课程示例中，从 V0 出发，先访问 V4，再沿 V4 -> V6 -> V7 深入；V7 没有未访问邻接点后回退，再从 V6 找到其他未访问顶点。

广度优先 BFS

BFS 的策略是“先访问当前顶点的所有邻接点，再处理下一层”。它通常使用队列。

flowchart TD
  A["起点入队并访问"] --> B["队头出队"]
  B --> C["访问其所有未访问邻接点并入队"]
  C --> D{"队列为空？"}
  D -->|否| B
  D -->|是| E["遍历结束"]

BFS 与二叉树层序遍历类似，但图可能有回路，所以必须记录是否访问过。

访问序列为什么可能不唯一

如果一个顶点有多个邻接点，先访问哪个邻接点会影响 DFS/BFS 序列。题目若给邻接矩阵或邻接表，就按存储顺序决定；若只给图形，通常按顶点编号或选项反推。

影响因素	说明
起始顶点	起点不同，序列不同
邻接点顺序	同一顶点多个邻接点时，选择顺序影响结果
存储结构	邻接表顺序会直接影响遍历序列
图是否连通	非连通图从一个顶点出发只能遍历所在连通分量

遍历复杂度

课程强调：遍历复杂度与存储结构有关，与 DFS/BFS 本身的“深/广”无关。

存储结构	复杂度	原因
邻接矩阵	$O(n^2)$	需要扫描矩阵行列判断邻接
邻接表	$O(n+e)$	访问顶点表和实际边表节点

判断是否遍历完成，可以用 count 记录已访问顶点数，直到 count == n。

本节例题

单选

关于图遍历，下列说法正确的是：

ADFS 必须使用队列BBFS 通常使用队列C图遍历不需要记录访问状态D邻接矩阵遍历复杂度一定是 O(n+e)

自查清单

1. 能否说出 DFS 和 BFS 的访问策略差别？
2. 能否解释为什么图遍历必须标记 visited？
3. 能否根据邻接矩阵/邻接表判断遍历复杂度？