图论算法
图论题描述的是一组事物和它们之间的连接，比如城市与道路，或者“课程表”里的课程和先修关系。只要看出题目背后的图，大部分问题都能对应到一个已知的算法。
九个章节依次是图的遍历、拓扑排序、最短路、最小生成树、欧拉路径、强连通与双连通分量、二分图染色、网络流，以及其他图论题。这是整条路线的最后一份题单，前提是你已经能熟练使用递归和 BFS。
109 道题难度分 1383–30289 章节
进入书房
想有人陪你把这份题单做完吗？登录后进入书房，女主角会一次递给你一道题。
一、图的遍历
§1.1 DFS
| 题目 | 难度分 |
|---|---|
| 547. 省份数量 | 1383 |
| 1971. 寻找图中是否存在路径 | 1397 |
| 797. 所有可能的路径 | 1383 |
| 1306. 跳跃游戏 III | 1397 |
| 841. 钥匙和房间 | 1412 |
| 2316. 统计无向图中无法互相到达点对数 | 1604 |
| 1319. 连通网络的操作次数 | 1633 |
| 2492. 两个城市间路径的最小分数 | 1680 |
| 3310. 移除可疑的方法 | 1711 |
| 2685. 统计完全连通分量的数量 | 1769 |
| 2192. 有向无环图中一个节点的所有祖先 | 1788 |
| 3387. 两天自由外汇交易后的最大货币数 | 1788 |
| 924. 尽量减少恶意软件的传播 | 1869 |
| 2101. 引爆最多的炸弹 | 1880 |
| 721. 账户合并 | 未评分 |
| 207. 课程表 | 未评分 |
| 802. 找到最终的安全状态 | 1962 |
| 3695. 交换元素后的最大交替和 | 1984 |
| 928. 尽量减少恶意软件的传播 II | 1985 |
| 2092. 找出知晓秘密的所有专家 | 2004 |
§1.2 BFS
| 题目 | 难度分 |
|---|---|
| 3243. 新增道路查询后的最短距离 I | 1568 |
| 1311. 获取你好友已观看的视频 | 1653 |
| 3015. 按距离统计房屋对数目 I | 1658 |
| 1129. 颜色交替的最短路径 | 1780 |
| 2039. 网络空闲的时刻 | 1865 |
| 2608. 图中的最短环 | 1904 |
| 815. 公交路线 | 1964 |
§1.3 图论建模 + BFS Shortest Path
| 题目 | 难度分 |
|---|---|
| 433. 最小基因变化 | 未评分 |
| 1284. 转化为全零矩阵的最少反转次数 | 1811 |
| 773. 滑动谜题 | 1815 |
| 752. 打开转盘锁 | 1878 |
| 301. 删除无效的括号 | 未评分 |
| 514. 自由之路 | 未评分 |
| 847. 访问所有节点的最短路径 | 2201 |
| 854. 相似度为 K 的字符串 | 2377 |
| 127. 单词接龙 | 未评分 |
| 488. 祖玛游戏 | 未评分 |
二、Topological Sort
§2.1 Topological Sort
| 题目 | 难度分 |
|---|---|
| 210. 课程表 II | 未评分 |
| 2115. 从给定原材料中找到所有可以做出的菜 | 1679 |
| 2392. 给定条件下构造矩阵 | 1961 |
| 802. 找到最终的安全状态 | 1962 |
| 1591. 奇怪的打印机 II | 2291 |
| 1203. 项目管理 | 2419 |
| 2603. 收集树中金币 | 2712 |
§2.2 在Topological Order上 DP
| 题目 | 难度分 |
|---|---|
| 851. 喧闹和富有 | 1783 |
| 2050. 并行课程 III | 2084 |
| 1857. 有向图中最大颜色值 | 2313 |
§2.3 Pseudotree
| 题目 | 难度分 |
|---|---|
| 2359. 找到离给定两个节点最近的节点 | 1715 |
| 2360. 图中的最长环 | 1897 |
| 684. 冗余连接 | 未评分 |
| 685. 冗余连接 II | 未评分 |
| 2876. 有向图访问计数 | 2210 |
| 2127. 参加会议的最多员工数 | 2449 |
| 2836. 在传球游戏中最大化函数值 | 2769 |
三、Shortest Path
§3.1 Single-Source Shortest Path：Dijkstra Algorithm
§3.2 All-Pairs Shortest Path：Floyd-Warshall Algorithm
| 题目 | 难度分 |
|---|---|
| 2642. 设计可以求最短路径的图类 | 1811 |
| 1334. 阈值距离内邻居最少的城市 | 1855 |
| 2976. 转换字符串的最小成本 I | 1882 |
| 2959. 关闭分部的可行集合数目 | 2077 |
| 2977. 转换字符串的最小成本 II | 2696 |
四、Minimum Spanning Tree
四、Minimum Spanning Tree
| 题目 | 难度分 |
|---|---|
| 1584. 连接所有点的最小费用 | 1858 |
| 1489. 找到最小生成树里的关键边和伪关键边 | 2572 |
五、Eulerian Path/Eulerian Circuit
五、Eulerian Path/Eulerian Circuit
| 题目 | 难度分 |
|---|---|
| 332. 重新安排行程 | 未评分 |
| 753. 破解保险箱 | 2274 |
| 2097. 合法重新排列数对 | 2651 |
六、Strongly Connected Components (SCC)/Biconnected Components
六、Strongly Connected Components (SCC)/Biconnected Components
| 题目 | 难度分 |
|---|---|
| 1192. 查找集群内的关键连接 | 2085 |
| 1568. 使陆地分离的最少天数 | 2209 |
七、Bipartite Coloring
七、Bipartite Coloring
| 题目 | 难度分 |
|---|---|
| 785. 判断二分图 | 1625 |
| 886. 可能的二分法 | 1795 |
八、Network Flow
八、Network Flow
| 题目 | 难度分 |
|---|---|
| 1947. 最大兼容性评分和 | 1704 |
| 3376. 破解锁的最少时间 I | 1793 |
| 2850. 将石头分散到网格图的最少移动次数 | 2001 |
| 1879. 两个数组最小的异或值之和 | 2145 |
| 1349. 参加考试的最大学生数 | 2386 |
| 2172. 数组的最大与和 | 2392 |
| 3276. 选择矩阵中单元格的最大得分 | 2403 |
| 1595. 连通两组点的最小成本 | 2538 |
| 3257. 放三个车的价值之和最大 II | 2553 |
九、其他
九、其他
| 题目 | 难度分 |
|---|---|
| 1042. 不邻接植花 | 1712 |
| 1761. 一个图中连通三元组的最小度数 | 2005 |
| 2508. 添加边使所有节点度数都为偶数 | 2060 |
| 1579. 保证图可完全遍历 | 2132 |
| 2065. 最大化一张图中的路径价值 | 2178 |
| 1697. 检查边长度限制的路径是否存在 | 2300 |
| 2242. 节点序列的最大得分 | 2304 |
| 2493. 将节点分成尽可能多的组 | 2415 |
| 1782. 统计点对的数目 | 2457 |
| 3666. 使二进制字符串全为 1 的最少操作次数 | 2477 |
| 2612. 最少翻转操作数 | 2824 |
| 3435. 最短公共超序列的字母出现频率 | 3028 |
| 466. 统计重复个数 | 未评分 |
这是路线上的最后一份题单；核心小节做完后，女主角会带你进入进阶题单，前面题单的选做小节都在那里等你。
难度分来自 zerotrac 的 LeetCode 竞赛评分。部分题目没有 zerotrac 分数，会标记为“未评分”。
进入书房