图的遍历与应用 · 融合风（象牙 + Obsidian 入口）

速查

DFS 用栈/递归（邻接矩阵 $O(n^2)$ / 邻接表 $O(n+e)$），BFS 用队列（同复杂度）；一次 DFS/BFS 访问一个连通分量，调用次数 = 连通分量数；拓扑排序仅 DAG 可行，失败 ⟺ 有环。

速查 ▾

项目	值
主题	图的遍历与应用
核心概念	从某一顶点出发，按某种策略访问图中所有顶点且只访问一次
时间复杂度	$O(n)$、$O(n+e)$、$O(n^2)$
难度	⭐⭐⭐
重要性	⭐⭐

核心概念 ▾

一、深度优先搜索（DFS）

类似树的先序遍历，使用递归或栈
时间复杂度：邻接矩阵 $O(n^2)$，邻接表 $O(n+e)$
空间复杂度：$O(n)$（递归栈 / 显式栈）

二、广度优先搜索（BFS）

类似树的层次遍历，使用队列
时间复杂度：邻接矩阵 $O(n^2)$，邻接表 $O(n+e)$
无权图 中 BFS 求出的就是边数最少的最短路径

三、图的连通性

对无向图进行一次 DFS/BFS 可访问一个连通分量的所有顶点
调用 DFS/BFS 的次数 = 连通分量数
对有向图，强连通分量 用 Kosaraju 或 Tarjan 算法

四、拓扑排序

仅适用于有向无环图（DAG）
方法：每次选择入度为 0 的顶点输出并删除其出边
若无法输出所有顶点，则图中存在环

一句话遍历是图几乎所有算法（连通性、拓扑排序、关键路径、最短路径）的共同基础。

关键定义 ▾

概念	定义
连通图	无向图中任意两顶点间存在路径
强连通图	有向图中任意两顶点互相可达
连通分量	无向图的极大连通子图
强连通分量	有向图的极大强连通子图
拓扑排序	DAG 中将顶点排成线性序列，使所有边从前指向后
AOE 网	边表示活动的带权有向图，用于关键路径分析
关键路径	AOE 网中源点到汇点的最长路径，决定工程最短工期

常见考法 ▾

考点	说明
DFS/BFS 遍历序列	给定图，写出从某顶点出发的 DFS 或 BFS 序列
判断连通分量数	对无向图执行 DFS，调用次数即为连通分量数
拓扑排序过程	每步选入度为 0 的顶点，写出排序序列；判断有无环
关键路径计算	求事件最早/最晚发生时间，活动最早/最晚开始时间
邻接矩阵 vs 邻接表	空间复杂度、边数查询、遍历效率的比较
存储结构选择	稠密图用邻接矩阵，稀疏图用邻接表

易错点 ▾

注意

有向图的连通性要区分弱连通与强连通
BFS 求出的仅是无权图最短路径（边权全为 1）
拓扑排序结果不唯一，每步可多选入度为 0 的顶点
关键路径上活动总时差为 0，但总时差为 0 的活动不一定在关键路径上
无向图邻接矩阵对称，有向图不一定对称
$n$ 个顶点有向图用邻接矩阵存储，空间复杂度始终为 $O(n^2)$

核心结论 ▾

无向图中所有顶点度之和 = $2e$（$e$ 为边数）
有向图中所有顶点出度之和 = 入度之和 = $e$
无向连通图至少有 $n-1$ 条边；有向强连通图至少有 $n$ 条边
DFS/BFS 时间复杂度：邻接矩阵 $O(n^2)$，邻接表 $O(n+e)$
拓扑排序失败 ⟺ 图中有环
$n$ 个顶点无向图最多 $n(n-1)/2$ 条边；有向图最多 $n(n-1)$ 条边

记忆卡片 ▾

DFS 和 BFS 的时间复杂度？

邻接矩阵 $O(n^2)$，邻接表 $O(n+e)$，$n$ 为顶点数，$e$ 为边数。

拓扑排序失败说明什么？

有向图中存在环（DAG 才能成功拓扑排序）。

DFS 与 BFS 的区别？

DFS 用栈/递归，深度优先；BFS 用队列，广度优先，适合求无权图最短路径。

无向连通图至少有多少条边？

$n-1$ 条（恰好是一棵生成树）。

边数与度数的关系？

无向图：边数 = 度数之和 / 2；有向图：边数 = 入度之和 = 出度之和。

连通分量数怎么求？

DFS/BFS 调用次数 = 连通分量数。

交互动画 · BFS 分层（无权图最短路径） ▾

从顶点 0 开始，逐层扩展

点击「播放」或「下一步」

BFS 每层到源点的距离 +1，因此树上第一次访问到的顶点对应的就是无权图最短路径（边数为层数）。

速查 ▾

核心概念 ▾

一、深度优先搜索（DFS）

二、广度优先搜索（BFS）

三、图的连通性

四、拓扑排序

关键定义 ▾

常见考法 ▾

易错点 ▾

核心结论 ▾

记忆卡片 ▾

交互动画 · BFS 分层（无权图最短路径） ▾

相关知识点