图
图用顶点与边表示连接、依赖和状态转换。本文负责图的表示、复杂度、连通性与权重选择。
1. 面试核心
先记住这几条，再读正文- 存储方式。 邻接表空间为 O(V+E)，适合稀疏图；邻接矩阵空间为 O(V²)，但可以在 O(1) 时间判断一条边是否存在。卡 · 顶点、方向与权重
- 无向连通性。 无向图按相互可达关系划分连通分量。一次完整搜索可找出起点所在分量，再从未访问节点继续即可遍历所有分量。
- 有向连通性。 有向图的强连通要求双向可达，单向搜索只给出可达集合。卡 · 连通分量与可达性
- 最短路条件。 非负权图可用 Dijkstra，普通 BFS 适用于等正权最短路。
2. 顶点、方向与权重
课程 A 是 B 的前置，可表示为 A → B。双向道路用无向边，单行道路用有向边。距离不同时，最少边数与最短距离是不同目标。
0: [1, 2]
1: [2]
2: []
这是有向邻接表，边为 0→1、0→2、1→2。线性扫描 0 的邻居即可查询 0→2。成本为 O(deg(0))，deg 表示出度。邻接矩阵查边为 O(1)，但需存储 V² 个位置。
3. 搜索与访问状态
邻接表完整搜索耗时 O(V+E)。矩阵逐行找邻居需 O(V²)。无向边各存两次，仍为 O(V+E) 空间。
入队时记录访问状态，可避免重复扩展。实现见树与图搜索。
4. 连通分量与可达性
无向图中，从一个顶点出发可访问其整个连通分量。遍历全体顶点，并对未访问点启动搜索，即可统计分量数。
有向图需要区分可达、弱连通和强连通。弱连通忽略边方向，强连通要求分量内任意两点互达。对 0→1，0 能到 1，1 却无法回到 0。它有一个弱连通分量、两个强连通分量。
在有向图上反复搜索并计数，会受起点顺序影响。强连通分量可按岗位需要学习 Tarjan 或 Kosaraju 算法。
5. 使用边界
隐式图需定义状态身份和合法邻居。网格节点可用行列坐标表示。路径枚举的状态恢复见回溯。
| 边权与目标 | 方法与条件 |
|---|---|
| 等正权最短路 | BFS 按边数扩展。 |
| 0 或 1 权重 | 0-1 BFS 用双端队列维护距离顺序。 |
| 非负权最短路 | Dijkstra 按当前最小距离扩展。 |
| 含负权最短路 | Bellman-Ford 可检测源点可达的负环。 |
若可达负环还能通往目标，可反复绕环降低路径代价。此时源点到目标没有有限的最短距离。
6 · 面试题卡片
本页题目与参考回答
6.1 邻接表和邻接矩阵如何选择？
考察重点：存储规模、查边和遍历邻居。
相关内容：顶点、方向与权重。
参考回答
稀疏图适合邻接表，空间为 O(V+E)。
矩阵查边为 O(1)，适合可容纳 V² 空间的频繁查边任务。完整遍历邻接表为 O(V+E)，扫描矩阵为 O(V²)。
6.2 有向图从一个起点搜索后，能得到强连通分量吗？
考察重点：单向可达与相互可达。
相关内容：连通分量与可达性。
参考回答
一次搜索得到起点的可达集合，其中节点未必互达。
0→1 就是反例。强连通分量要求任意两点都能互相到达，需要专门的分量算法。
6.3 边权改变时，最短路径算法如何选择？
考察重点：等权、非负权与负环。
相关内容：使用边界。
参考回答
等正权可用 BFS，0/1 权可用 0-1 BFS。
一般非负权可用 Dijkstra，含负权可用 Bellman-Ford。可达负环若还能通往目标，就没有有限最短距离。