考研笔记

图的遍历

BFS 和 DFS 你闭着眼睛能写，这一节要补的是三样教材专属的东西：复杂度与存储结构的关系、生成树/生成森林、遍历次数与连通分量。

机制

两种遍历

数据结构思想
广度优先搜索（BFS）队列先访问起始顶点，再访问其所有邻接顶点，再依次访问这些顶点的未访问邻接点——一层一层向外扩
深度优先搜索（DFS）栈（或递归）访问一个顶点后，沿一条路径尽可能深入，走不通再回溯

两者都需要一个 visited[] 数组标记访问状态，保证每个顶点只被访问一次。

复杂度取决于存储结构

这是本节最容易被算竞直觉带偏的一条：时间复杂度不是「」一句话就完了。

邻接矩阵邻接表
BFS 时间
DFS 时间
空间（队列 / 栈）

邻接矩阵下要找一个顶点的所有邻接点，必须扫完整整一行，即 ， 个顶点各扫一次就是 。

口径差异：

算竞里存图默认是邻接表，所以 BFS/DFS 的复杂度被当成常识写作 ，从不提存储结构。 408 恰恰把「邻接矩阵 / 邻接表 」当成两个独立的答案来考， 选项里两个都会出现。看到问复杂度先看题目给的是哪种存储。

BFS 与最短路径

对无权图，BFS 求得的是从起点出发的最短路径（边数最少的路径）——这是 BFS 的一个直接推论，因为它按层扩展。

但对带权图，BFS 不能求最短路径，要用 Dijkstra。

生成树与生成森林

由遍历过程中经过的边构成的树。

  • 广度优先生成树：BFS 过程中，从每个已访问顶点出发首次到达某顶点所用的边。
  • 深度优先生成树：DFS 过程中同理。

边界辨析：

邻接矩阵下生成树唯一，邻接表下不唯一。 因为邻接矩阵的邻接点顺序由下标固定，而邻接表的边表次序取决于边的输入顺序（6.2.2 性质 ⑤）。 这条与 6.2「邻接矩阵表示唯一、邻接表不唯一」是同一个根源的两次兑现。

对非连通图，遍历会产生生成森林：每个连通分量对应生成森林中的一棵树。

遍历与连通性

这是本节最好用的一条结论：

图的类型结论
无向图调用 BFS/DFS 的次数 连通分量数。连通图只需调用一次
有向图调用次数与起点选择有关；从某顶点出发一次遍历能访问全部顶点，说明该顶点到其余各顶点都有路径

边界辨析：

有向图里「一次遍历访问到所有顶点」不等于「强连通」。 它只说明存在从该顶点到所有顶点的路径，反向路径未必存在。 有向图是强连通图的充要条件是从任一顶点出发都能一次遍历访问全部顶点。

手算模板

写 BFS / DFS 序列：

  1. 先确认邻接点的访问次序——题目通常规定「按顶点编号从小到大」或直接给邻接表。这一步定了，序列才唯一。
  2. BFS：起点入队 → 出队访问 → 未访问邻接点依次入队 → 重复。
  3. DFS：访问 → 找第一个未访问邻接点递归 → 无路可走则回溯。
  4. 写完检查：序列长度 该连通分量的顶点数。

画生成树：把「首次访问某顶点时所用的那条边」画出来，其余边（回边/交叉边）不画。生成树一定有 条边（ 为该连通分量的顶点数）。

数连通分量：无向图中，主函数里 for 循环真正发起遍历的次数就是连通分量数。

边界

说法判断说明
「BFS 用栈」❌队列；DFS 用栈
「遍历的时间复杂度是 」⚠️只在邻接表下；邻接矩阵是
「BFS 能求带权图的最短路径」❌只对无权图；带权要用 Dijkstra
「广度优先生成树唯一」⚠️邻接矩阵下唯一，邻接表下不唯一
「生成树包含图的所有边」❌只含 条首次到达的边
「非连通图遍历得到生成树」❌得到生成森林
「无向图遍历调用次数与起点有关」❌等于连通分量数，与起点无关
「有向图一次遍历访问完所有顶点即强连通」❌只说明该顶点可达所有顶点
「DFS 序列唯一」❌取决于邻接点的访问次序
「BFS 和 DFS 都能判断图是否有环」✅但有向图判环通常用拓扑排序

对照速查

BFSDFS
结构队列栈 / 递归
邻接矩阵时间
邻接表时间
空间
副产品无权图最短路径拓扑排序、判环
生成树广度优先生成树深度优先生成树
结论内容
无向图遍历次数 连通分量数
生成树边数
非连通图得到生成森林
生成树唯一性邻接矩阵唯一，邻接表不唯一

考点

  • 邻接矩阵与邻接表下复杂度不同——选项里两个都会出现。
  • BFS 用队列、DFS 用栈。
  • BFS 只对无权图求最短路径。
  • 遍历调用次数 = 连通分量数。
  • 生成树 / 生成森林，以及唯一性与存储结构的关系。
  • 有向图「可达所有顶点」≠「强连通」。

链接

反向链接