跳到主要内容

图论

学完这一节，你应该能够

把关系建成图，再根据边权、方向和连通性选择遍历或路径算法。

前置知识

  • 基础数据结构
  • 递归、搜索与回溯
  • 树

解题框架

  1. 图的表示与遍历
  2. 有向依赖与拓扑排序
  3. 连通性、并查集与二分图
  4. 最短路
  5. 最小生成树
  6. 图论综合

母题路线

层级解题框架题目站内题解
必学图的表示与遍历LeetCode 1971. 寻找图中是否存在路径阅读题解
必学图的表示与遍历LeetCode 200. 岛屿数量阅读题解
必学图的表示与遍历LeetCode 133. 克隆图阅读题解
必学图的表示与遍历LeetCode 841. 钥匙和房间阅读题解
必学图的表示与遍历LeetCode 994. 腐烂的橘子阅读题解
必学有向依赖与拓扑排序LeetCode 207. 课程表阅读题解
必学有向依赖与拓扑排序LeetCode 210. 课程表 II阅读题解
必学连通性、并查集与二分图LeetCode 547. 省份数量阅读题解
必学连通性、并查集与二分图LeetCode 684. 冗余连接阅读题解
必学连通性、并查集与二分图LeetCode 785. 判断二分图阅读题解
必学最短路AcWing 849. Dijkstra求最短路 I阅读题解
必学最短路LeetCode 743. 网络延迟时间阅读题解
必学最短路AcWing 854. Floyd求最短路阅读题解
必学最小生成树AcWing 859. Kruskal算法求最小生成树阅读题解
必学最小生成树LeetCode 1584. 连接所有点的最小费用阅读题解
拓展图论综合LeetCode 399. 除法求值阅读题解
拓展图论综合LeetCode 909. 蛇梯棋阅读题解
拓展图论综合LeetCode 802. 找到最终的安全状态阅读题解
拓展图论综合LeetCode 310. 最小高度树阅读题解
拓展图论综合LeetCode 721. 账户合并阅读题解
拓展图论综合LeetCode 787. K 站中转内最便宜的航班阅读题解
拓展图论综合LeetCode 1631. 最小体力消耗路径阅读题解
拓展图论综合LeetCode 332. 重新安排行程阅读题解

下一章： 贪心

第八章学习路线​

先完成 15 道必学题，再按需要进入 8 道拓展题。六段路线依次是：

  1. 图的表示与遍历：把关系、网格和扩散过程统一成邻接表与搜索状态。
  2. 有向依赖与拓扑排序：用入度和队列处理先后约束。
  3. 连通性、并查集与二分图：建立连通块、合并语义与染色不变量。
  4. 最短路：根据图的稠密度、边权和查询范围选择 Dijkstra 或 Floyd。
  5. 最小生成树：从切分性质出发，连接全部顶点并控制总代价。
  6. 图论综合：把反图、分层松弛、状态图和欧拉路径迁移到新问题。

其中 并查集 是 Kruskal 判断一条边能否接入当前生成树的前置工具；先理解合并返回值的语义，再练习最小生成树。