02.4.2 图论与并查集
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图
这个知识域解决什么问题
图是多对多关系的抽象。本知识域围绕 图表示与遍历 → 拓扑排序与环检测 → 并查集 → 最短路径与最小生成树 四条主线展开;先建立邻接表/邻接矩阵与 DFS/BFS 框架,再处理依赖顺序、动态连通与网络代价问题。
知识地图
图表示与 DFS/BFS(1)
→ 拓扑排序与环检测(2)
→ 并查集(3)
→ 最短路径与最小生成树(4)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.4.2.1 | 图表示与 DFS/BFS | 邻接表/矩阵、DFS 递归与迭代、BFS、visited 时机、连通分量、岛屿、克隆图、二分图、多源 BFS | 20 |
| 02.4.2.2 | 拓扑排序与环检测 | Kahn 入度算法、DFS 逆后序、三色判环、课程表、拓扑唯一性、DAG 性质与关键路径 | 20 |
| 02.4.2.3 | 并查集 | find 根、路径压缩、按秩/大小合并、连通分量、冗余连接、账户合并、等式判定、α(n) 复杂度 | 20 |
| 02.4.2.4 | 最短路径与最小生成树 | BFS 无权最短路、Dijkstra、Bellman-Ford、Floyd、Kruskal、Prim、负权负环、网络延迟 | 20 |
合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径与边界条件。
学习路径
先 1 掌握图表示与两种遍历框架,2 用拓扑排序处理依赖与判环,3 用并查集解决动态连通与归并,最后 4 按权值条件选择最短路与 MST 算法。
自检
- [ ] 能根据边密度选择邻接表或邻接矩阵,并写出 DFS/BFS
- [ ] 能解释 visited 入结构即标记的原因
- [ ] 能手写 Kahn 拓扑排序并判环,理解 DFS 逆后序
- [ ] 能实现路径压缩 + 按秩合并的并查集,报出 α(n) 复杂度
- [ ] 能区分 Dijkstra、Bellman-Ford、Floyd 的适用条件
- [ ] 能写 Kruskal(DSU 判环)与 Prim,并说明选型
- [ ] 每题能报出时间、空间与口径,并列边界用例