图
共 30 条分类条目，8 个题型小节； 每行标注难度、题号、原笔记摘要和 LeetCode 链接。
一、图的基础与遍历（DFS/BFS）
5 条类型特点：这是图论最基础的操作。需要掌握如何构建图（邻接表/邻接矩阵），以及如何用 DFS/BFS 遍历图。很多复杂问题都是在此基础上扩展的。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 简单 | 1971. 寻找图中是否存在路径#1971 LeetCode ↗ | DFS/BFS/并查集判断两点是否连通 |
| 中等 | 133. 克隆图#133 LeetCode ↗ | DFS/BFS + 哈希表记录已克隆节点 |
| 中等 | 841. 钥匙和房间#841 LeetCode ↗ | DFS/BFS 遍历，判断能否访问所有房间 |
| 中等 | 797. 所有可能的路径#797 LeetCode ↗ | DFS 回溯，记录从源点到目标的所有路径 |
| 中等 | 547. 省份数量#547 LeetCode ↗ | DFS/BFS/并查集统计连通分量个数 |
- 简单#1971
DFS/BFS/并查集判断两点是否连通
- 中等#133
DFS/BFS + 哈希表记录已克隆节点
- 中等#841
DFS/BFS 遍历，判断能否访问所有房间
- 中等#797
DFS 回溯，记录从源点到目标的所有路径
- 中等#547
DFS/BFS/并查集统计连通分量个数
二、拓扑排序
5 条类型特点：用于处理有向无环图（DAG） 中任务的依赖关系。核心思想是不断删除入度为 0 的节点（Kahn 算法）或使用 DFS 后序记录。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 中等 | 207. 课程表#207 LeetCode ↗ | 拓扑排序判断是否有环（能否完成所有课程） |
| 中等 | 210. 课程表 II#210 LeetCode ↗ | 拓扑排序返回一种合理的课程顺序 |
| 中等 | 1462. 课程表 IV#1462 LeetCode ↗ | Floyd 或 DFS 预处理课程间的先修关系 |
| 困难 | 1203. 项目管理#1203 LeetCode ↗ | 两次拓扑排序（组间+组内） |
| 中等 | LeetCode ↗ | 拓扑排序，将食谱看作依赖关系 |
- 中等#207
拓扑排序判断是否有环（能否完成所有课程）
- 中等#210
拓扑排序返回一种合理的课程顺序
- 中等#1462
Floyd 或 DFS 预处理课程间的先修关系
- 困难#1203
两次拓扑排序（组间+组内）
- 中等#2115
拓扑排序，将食谱看作依赖关系
三、并查集（Union-Find）
5 条类型特点：高效处理动态连通性问题，支持合并集合和查询所属集合。核心操作是 find（路径压缩）和 union（按秩合并）。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 中等 | 684. 冗余连接#684 LeetCode ↗ | 并查集，当发现两个节点已连通时，当前边即为冗余边 |
| 中等 | 721. 账户合并#721 LeetCode ↗ | 将邮箱作为节点，用并查集合并属于同一账户的邮箱 |
| 中等 | 990. 等式方程的可满足性#990 LeetCode ↗ | 先将相等关系的变量合并，再检查不等关系是否矛盾 |
| 中等 | 1319. 连通网络的操作次数#1319 LeetCode ↗ | 并查集统计连通分量个数，所需操作数 = 分量数 - 1 |
| 困难 | LeetCode ↗ | 将行号和列号作为节点合并，最多移除数 = 总石头数 - 连通分量数 |
- 中等#684
并查集，当发现两个节点已连通时，当前边即为冗余边
- 中等#721
将邮箱作为节点，用并查集合并属于同一账户的邮箱
- 中等#990
先将相等关系的变量合并，再检查不等关系是否矛盾
- 中等#1319
并查集统计连通分量个数，所需操作数 = 分量数 - 1
- 困难#947
将行号和列号作为节点合并，最多移除数 = 总石头数 - 连通分量数
四、最短路径
6 条类型特点：求图中两点之间的最短路径。根据边权特点选择不同算法：
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 中等 | 743. 网络延迟时间#743 LeetCode ↗ | Dijkstra 标准模板 |
| 中等 | 1631. 最小体力消耗路径#1631 LeetCode ↗ | 二分答案 + BFS/DFS，或 Dijkstra 变种 |
| 中等 | 1514. 概率最大的路径#1514 LeetCode ↗ | Dijkstra 变种（求乘积最大值） |
| 中等 | LeetCode ↗ | Bellman-Ford 或 BFS + DP |
| 中等 | 1334. 阈值距离内邻居最少的城市#1334 LeetCode ↗ | Floyd-Warshall 多源最短路径 |
| 中等 | 542. 01 矩阵#542 LeetCode ↗ | 多源 BFS（所有0同时入队） |
- 中等#743
Dijkstra 标准模板
- 中等#1631
二分答案 + BFS/DFS，或 Dijkstra 变种
- 中等#1514
Dijkstra 变种（求乘积最大值）
- 中等#787
Bellman-Ford 或 BFS + DP
- 中等#1334
Floyd-Warshall 多源最短路径
- 中等#542
多源 BFS（所有0同时入队）
五、最小生成树（MST）
3 条类型特点：在连通加权图中寻找一棵树，连接所有节点且总权值最小。常用算法：
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 中等 | 1584. 连接所有点的最小费用#1584 LeetCode ↗ | Kruskal 或 Prim 模板 |
| 中等 | 1135. 最低成本联通所有城市#1135 LeetCode ↗ | Kruskal 模板 |
| 困难 | LeetCode ↗ | 最小生成树 + 枚举判断 |
- 中等#1584
Kruskal 或 Prim 模板
- 中等#1135
Kruskal 模板
- 困难#1489
最小生成树 + 枚举判断
六、二分图
2 条类型特点：判断图是否能分成两个集合，使得集合内部无边（即所有边连接两个不同集合）。可用染色法（DFS/BFS）解决。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 中等 | 785. 判断二分图#785 LeetCode ↗ | 染色法 BFS/DFS |
| 中等 | 886. 可能的二分法#886 LeetCode ↗ | 建图后判断二分图 |
- 中等#785
染色法 BFS/DFS
- 中等#886
建图后判断二分图
七、强连通分量 & 割点/桥
2 条类型特点：进阶图论问题，通常需要 Tarjan 算法找强连通分量（SCC）或关键连接。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 困难 | 1192. 查找集群内的关键连接#1192 LeetCode ↗ | Tarjan 算法找桥（边） |
| 困难 | 1568. 使陆地分离的最少天数#1568 LeetCode ↗ | 结合连通分量计数和 Tarjan 思想 |
- 困难#1192
Tarjan 算法找桥（边）
- 困难#1568
结合连通分量计数和 Tarjan 思想
八、欧拉路径/回路
2 条类型特点：寻找一条路径经过每条边恰好一次（一笔画问题）。常用 Hierholzer 算法。
| 难度 | 题目 | 核心思路（原笔记摘要） |
|---|---|---|
| 困难 | 332. 重新安排行程#332 LeetCode ↗ | Hierholzer 算法找欧拉路径 |
| 困难 | 753. 破解保险箱#753 LeetCode ↗ | 将密码看作边，找欧拉回路 |
- 困难#332
Hierholzer 算法找欧拉路径
- 困难#753
将密码看作边，找欧拉回路