图的表示与 BFS/DFS 遍历
一句话定义
图（Graph）G=(V,E) 由顶点集与边集构成（有向/无向、带权/无权）；邻接表/邻接矩阵是两种基本表示，广度优先搜索（BFS）按层扩展、深度优先搜索（DFS）一探到底，二者都在 O(V+E) 内遍历全图，是所有图算法的骨架。
为什么重要
图是「任意二元关系」的通用模型：社交网络、依赖关系、路网、状态机。本模块的其余算法（最短路、MST、拓扑、二分图、网络流）全部构建在「表示 + BFS/DFS」这块地基上；BFS 求无权最短路、DFS 求连通性与环，本身就是高频面试与工程题。visited 标记、队列/栈的选择这些肌肉记忆，从这里开始建立。
前置知识
kp-008（队列/栈）；kp-011（树遍历——图遍历是它的带环推广）。
核心概念
- 术语：度（无向）/入度出度（有向）、路径、环、连通、子图；稀疏图 E≈O(V)，稠密图 E≈O(V²)。
- 邻接表：每顶点一个邻居列表（数组 of 列表），空间 O(V+E)，遍历邻居快，适合稀疏图——工程默认。
- 邻接矩阵：n×n 0/1（或权值）矩阵，空间 O(V²)，查「u,v 是否相邻」O(1)，适合稠密图或频繁邻接查询。
- BFS：队列 + visited；从源点分层扩展，首次到达某点的层数即无权最短距离。
- DFS：递归或显式栈 + visited；产生深度优先森林，进入/离开时间戳（括号结构）支持拓扑序、割点桥等推导。
- 复杂度：两者均 Θ(V+E)（邻接表）；矩阵表示则 Θ(V²)。
直观类比
BFS 是往池塘里丢石头看波纹，一圈圈往外扩，第一次碰到即最短距离；DFS 是走迷宫时「贴一面墙一直走到底再回头」，把一条支路彻底探索完才换下一条。
原理与机制
BFS 伪代码（无权最短距离）：
函数 BFS(s):
dist[全部] ← ∞ ; dist[s] ← 0 ; 队列 ← [s]
当 队列非空:
u ← 出队
对于 v ∈ adj[u]:
若 dist[v] == ∞:
dist[v] ← dist[u] + 1 ; v 入队正确性核心：队列单调（距离值只增不减、至多两种相邻值），顶点按距离非降序出队，故首次入队的 dist 即最短跳数——证明要点是「归纳于层」。DFS 的时间戳性质：u 是 v 的祖先 ⇔ [in(u), out(u)] ⊇ [in(v), out(v)]（括号定理），它直接导出拓扑排序与 kp-019 的 SCC 算法。
图示
图: A ─ B ─ C 邻接表:
| | A: [B, D]
D ─ E B: [A, C, E]
C: [B]
从 A 出发: D: [A, E]
BFS 层次: A → {B,D} → {C,E} E: [B, D]
dist: A=0, B=D=1, C=E=2
DFS(先访字母序): A→B→C 回溯→E→D（栈序）实例或案例
- 社交网络「几度人脉」：BFS 层数即度数；LinkedIn 的二度连接。
- 迷宫最短步数、棋盘马走日最少步数：格子图上 BFS。
- 爬虫与垃圾回收（可达性标记）：DFS/BFS 遍历引用图。
- 编译依赖、课程先修：有向图判环（DFS 回边）或拓扑排序（kp-018）。
常见误区
- 忘记 visited 标记：有环图无限循环；标记时机应在「入队/入栈时」而非出队后（否则同一节点重复入队，复杂度劣化）。
- 无向图只加单向边：邻接表必须 u→v、v→u 双向注册，这是最高频的实现 bug。
- 递归 DFS 在深图上栈溢出：V 可达 10⁵~10⁶ 时应显式栈化。
- 用 BFS 去解带权最短路：层数 ≠ 权和，带权必须换 Dijkstra（kp-017）。
自测题
- 对上图从 E 出发写 BFS 序与各点最短跳数。
答案要点：E=0；B=1, D=1；A=2（经 D 或 B）, C=2（经 B）。
- 无向图邻接表与邻接矩阵的空间各是多少？何时选矩阵？
答案要点：O(V+2E)=O(V+E) 与 O(V²)；E≈V² 的稠密图或需要 O(1) 邻接判定时选矩阵。
- 如何用 DFS 判断有向图是否有环？
答案要点：三色标记，遇到「灰色」回边（当前递归栈中的节点被再次访问）即有环。
与其他知识点的关系
kp-017 在 BFS 的分层思想上加权升级；kp-018 拓扑排序直接用 DFS 完成时间；kp-030 并查集是「只要连通性不要遍历路径」时的省力替代；kp-027 回溯与 DFS 的关系是「图遍历求可达 vs 决策树遍历求全部解」。
延伸阅读
《算法导论》第 20 章（20.2/20.3 BFS 与 DFS）；《算法（第 4 版）》第 4.1–4.2 节（无向/有向图）。