文章目录图论灵魂拷问思维图论问题连通块问题DFS染色法并查集边带权的并查集判断是否有环DFS三色判定法。拓扑排序判定是否存在负环Bellman算法更新次数大于n-1SPFA算法更新次数大于n-1标准最短路问题最短路问题的建模最小修改次数问题将字符串A变为字符串B的最短路问题数独跳跃游戏网格图问题2D坐标-1D坐标坐标图问题坐标手动编号-[1,n]利用最短路辅助解决问题二分图应用未完待续寻找互不冲突的两个组寻找一一配对例题图论题单灵魂拷问DAG或者UDAG是否有重边或者自环从根节点或者其他节点开始是否一样是否存在多个连通块思维反向构造图完全图只保留有用边图论问题连通块问题DFS染色法将每一个块染色。并查集边带权的并查集边带权连通块的数量。所有的信息在根节点上。判断是否有环DFS三色判定法。**为什么需要三种颜色**遍历过且无环的节点为2遍历过但有环路径上的节点为1。dfs判定环看是否有重复遍历。但有重复遍历不一定有环。拓扑排序拓扑排序适合于有向无环的图如果无法输出全部结点说明有环判定是否存在负环Bellman算法更新次数大于n-1额外增加一次循环(表示长度为n)的路径如果更新则存在负环。SPFA算法更新次数大于n-1使用count记录更新次数。注意存在多个连通块因此必须让每个节点都入对列保证检查每一个连通块的负环情况。标准最短路问题BFS等权重最短路。在这种情况下BFS的效率是最高的Floyd多源最短路问题最短路问题的建模最小修改次数问题将字符串A变为字符串B的最短路问题数独比较适用于双向BFS状态为当前串。给定可以转移的状态列表给出从状态A转换为状态B的最短路径本质是BFS。矩阵相关注意先将矩阵转换为字符串然后按照正常的BFS来搜索跳跃游戏状态为当前位置最优性原理所有节点不会重复遍历且遍历过即最优。网格图问题2D坐标-1D坐标所给出的图是一个nxm的网格当作一般的图即可使用邻接矩阵存储。一般下一次添加的节点是相邻节点。网格/坐标图中邻接矩阵的构建一般采用imj / 手动编号(0~nm-1)的方式。不要暴力使用map构造pairint,int的映射坐标图问题坐标手动编号-[1,n]利用最短路辅助解决问题2972转换字符串的最小成本这题字符串长度为1e5状态数过多用dj和bfs不可能过。但我们可以使用暴力的方法求出每一步转换的最小成本然后利用最短路求出这些所有转换成本最终解决。二分图应用未完待续寻找互不冲突的两个组DFS二分图染色判定。寻找一一配对每一个配对都是二分图中的匹配。匈牙利二分图匹配算法。例题一、图的遍历§1.1 深度优先搜索DFS寻找有环三色标记法原因是为了区分不同的连通块和遍历起点(有向图)。DFS适合搜索所有可能的路径但不适用于最短路问题。分类题号题目备注连通块基础547省份数量重要连通块基础1971寻找图中是否存在路径重要连通块基础841钥匙和房间重要连通块基础1319连通网络的操作次数扩展连通块基础2316统计无向图中无法互相到达点对数扩展连通块基础2492两个城市间路径的最小分数扩展连通块基础2685统计完全连通分量的数量扩展路径搜索797所有可能的路径重要路径搜索LCP 07传递信息扩展路径搜索1306跳跃游戏 III扩展DAG / 拓扑相关207课程表重要DAG / 拓扑相关802找到最终的安全状态重要DAG / 拓扑相关2192有向无环图中一个节点的所有祖先扩展图上扩散 / 传播2101引爆最多的炸弹扩展图上扩散 / 传播924尽量减少恶意软件的传播扩展并查集可替代 DFS721账户合并扩展删除3387两天自由外汇交易后的最大货币数难度偏高 / 综合技巧删除3695交换元素后的最大交替和难度偏高删除928尽量减少恶意软件的传播 II2000删除2092找出知晓秘密的所有专家2000删除3108带权图里旅途的最小代价2000删除3310移除可疑的方法题型偏综合删除261以图判树会员题删除323无向图中连通分量的数目会员题一、BFS 最短路边权为 1边权为1使用BFS最快。分类 题号 题目 备注基础单源 BFS 3243 新增道路查询后的最短距离 I 重要基础单源 BFS 1311 获取你好友已观看的视频 重要多源 / 全源 BFS 3015 按距离统计房屋对数目 I 重要状态图 BFS 1129 颜色交替的最短路径 经典 / 分层状态建图转换 815 公交路线 经典 / 超时风险低环检测 BFS 2608 图中的最短环 扩展综合模拟 2039 网络空闲的时刻 扩展会员题跳过 3807 修复边以遍历图的最小成本 会员题以下是对该题单的二次筛选结果保留最具代表性、适合进一步练习的题目一、图论建模 BFS 最短路最短路最短距离最短修改次数这种说法可以建模为图论的最短路问题转化数字的最小运算数 开锁次数转化数字的最小运算数BFS和双向BFS仅适用于有限状态数的最短路问题状态的数量等于时间复杂度状态的定义数独华容道分类 题号 题目 备注基础状态建模 433 最小基因变化 重要基础状态建模 752 打开转盘锁 重要矩阵状态 BFS 1284 转化为全零矩阵的最少反转次数 重要矩阵状态 BFS 773 滑动谜题 重要字符串状态 BFS 127 单词接龙 重要 / 建议双向 BFS字符串状态 BFS 301 删除无效的括号 经典扩展字符串状态 BFS 854 相似度为 K 的字符串 难度偏高 / 剪枝练习图论状压 847 访问所有节点的最短路径 经典 / 状态压缩跳跃游戏类 1345 跳跃游戏 IV 重要跳跃游戏类 2059 转化数字的最小运算数 重要跳跃游戏类 1654 到家的最少跳跃次数 经典 / 有界 BFS跳跃游戏类 2998 使 X 和 Y 相等的最少操作次数 扩展跳跃游戏类 3629 通过质数传送到达终点的最少跳跃次数 扩展会员题跳过 1197 进击的骑士 会员题会员题跳过 3141 最大汉明距离 会员题综合 / 较难 488 祖玛游戏 难度偏高 / 模拟复杂综合 / 较难 514 自由之路 难度偏高 / 环形 DPBFS综合 / 较难 3690 拆分合并数组 难度偏高二、拓扑排序分类 题号 题目 备注前置理解 1557 可以到达所有点的最少点数目 重要 / 理解入度为0的点基础拓扑排序 210 课程表 II 重要 / 输出拓扑序基础拓扑排序 802 找到最终的安全状态 重要 /反向图思维拓扑 建图 2115 从给定原材料中找到所有可以做出的菜 经典 / 依赖关系建模拓扑 矩阵 2392 给定条件下构造矩阵 扩展 / 行列双拓扑拓扑 贪心 310 最小高度树 经典 / 剥洋葱法拓扑 验证 1361 验证二叉树 重要 / 入度出度判定难度偏高跳过 1591 奇怪的打印机 II 2291分 / 复杂模拟难度偏高跳过 1203 项目管理 2419分 / 双层拓扑难度偏高跳过 1632 矩阵转换后的排名 2530分 / 并查集拓扑难度偏高跳过 2603 收集树中金币 2712分 / 复杂树形DP会员题跳过 444 序列重建 会员题会员题跳过 269 / LCR 114 火星词典 会员题会员题跳过 2371 最小化网格中的最大值 会员题会员题跳过 3481 应用替换 会员题三、在拓扑序上 DP选作拓扑序DP分类 题号 题目 备注基础拓扑DP 851 喧闹和富有 重要 / 刷表法入门基础拓扑DP 2050 并行课程 III 重要 / 最长路径DP进阶拓扑DP 1857 有向图中最大颜色值 经典 / 颜色计数DP会员题跳过 1136 并行课程 会员题难度偏高跳过 3620 恢复网络路径 题目信息不完整以下是对该题单的二次筛选结果保留最具代表性、难度适中、降低解法重复的题目。三、最短路§3.1 单源最短路Dijkstra 算法分类 题号 题目 备注基础入门 743 网络延迟时间 重要 / 标准模板题基础入门 3341 到达最后一个房间的最少时间 I 重要 / 网格图Dijkstra入门理解原理 3112 访问消失节点的最少时间 重要 / 理解节点失效时间设计类 2642 设计可以求最短路径的图类 重要 / Dijkstra类的设计概率类 1514 概率最大的路径 经典 / 乘积转加法网格图 1631 最小体力消耗路径 经典 / 多种解法网格图 778 水位上升的泳池中游泳 经典 / 与1631类似但不同网格图 2577 在网格图中访问一个格子的最少时间 扩展 / 时间依赖等待计数类 1976 到达目的地的方案数 经典 / 最短路计数第二短路径 2045 到达目的地的第二短时间 经典 / BFS也可K站中转 787 K站中转内最便宜的航班 经典 / 与1928类似选更经典的动态规划 1928 规定时间内到达终点的最小花费 扩展 / DPDijkstra赛车 818 赛车 难度偏高 / 状态图BFSDP分层图 LCP 35 电动车游城市 经典 / 分层图入门SPFA/差分约束 2589 完成所有任务的最少时间 扩展 / 差分约束§3.2 全源最短路Floyd 算法Floyd 算法本质是三维 DP。理解 DP 一定要基于空间优化前的写法。转换字符串的最小成本这题不能用BFS来做状态空间很大。不过可以抽象为最短路来做先单独求解每一个字符转换的最小成本。因为有多个字符所以使用多源最短路算法。–2642. 设计可以求最短路径的图类 1811 动态加边1334. 阈值距离内邻居最少的城市 18552976. 转换字符串的最小成本 I 18822959. 关闭分部的可行集合数目 20772977. 转换字符串的最小成本 II 2696四、最小生成树涉及到 Kruskal 算法和 Prim 算法。前者一般用于稀疏图后者一般用于稠密图。一般使用堆优化的Krusal算法。最小带权和的生成树。–1584. 连接所有点的最小费用 18583600. 升级后最大生成树稳定性 2301 做法不止一种二分Krusal算法1489. 找到最小生成树里的关键边和伪关键边 25721135. 最低成本连通所有城市会员题1168. 水资源分配优化会员题七、二分图染色二分图两个节点连边。典型例题分组织问题。模板交替染色法785. 判断二分图 1625786. 可能的二分法 1795787. 最大划分因子 2135只保留有用的边二分
图论·刷题总结
发布时间：2026/5/21 15:11:38
文章目录图论灵魂拷问思维图论问题连通块问题DFS染色法并查集边带权的并查集判断是否有环DFS三色判定法。拓扑排序判定是否存在负环Bellman算法更新次数大于n-1SPFA算法更新次数大于n-1标准最短路问题最短路问题的建模最小修改次数问题将字符串A变为字符串B的最短路问题数独跳跃游戏网格图问题2D坐标-1D坐标坐标图问题坐标手动编号-[1,n]利用最短路辅助解决问题二分图应用未完待续寻找互不冲突的两个组寻找一一配对例题图论题单灵魂拷问DAG或者UDAG是否有重边或者自环从根节点或者其他节点开始是否一样是否存在多个连通块思维反向构造图完全图只保留有用边图论问题连通块问题DFS染色法将每一个块染色。并查集边带权的并查集边带权连通块的数量。所有的信息在根节点上。判断是否有环DFS三色判定法。**为什么需要三种颜色**遍历过且无环的节点为2遍历过但有环路径上的节点为1。dfs判定环看是否有重复遍历。但有重复遍历不一定有环。拓扑排序拓扑排序适合于有向无环的图如果无法输出全部结点说明有环判定是否存在负环Bellman算法更新次数大于n-1额外增加一次循环(表示长度为n)的路径如果更新则存在负环。SPFA算法更新次数大于n-1使用count记录更新次数。注意存在多个连通块因此必须让每个节点都入对列保证检查每一个连通块的负环情况。标准最短路问题BFS等权重最短路。在这种情况下BFS的效率是最高的Floyd多源最短路问题最短路问题的建模最小修改次数问题将字符串A变为字符串B的最短路问题数独比较适用于双向BFS状态为当前串。给定可以转移的状态列表给出从状态A转换为状态B的最短路径本质是BFS。矩阵相关注意先将矩阵转换为字符串然后按照正常的BFS来搜索跳跃游戏状态为当前位置最优性原理所有节点不会重复遍历且遍历过即最优。网格图问题2D坐标-1D坐标所给出的图是一个nxm的网格当作一般的图即可使用邻接矩阵存储。一般下一次添加的节点是相邻节点。网格/坐标图中邻接矩阵的构建一般采用imj / 手动编号(0~nm-1)的方式。不要暴力使用map构造pairint,int的映射坐标图问题坐标手动编号-[1,n]利用最短路辅助解决问题2972转换字符串的最小成本这题字符串长度为1e5状态数过多用dj和bfs不可能过。但我们可以使用暴力的方法求出每一步转换的最小成本然后利用最短路求出这些所有转换成本最终解决。二分图应用未完待续寻找互不冲突的两个组DFS二分图染色判定。寻找一一配对每一个配对都是二分图中的匹配。匈牙利二分图匹配算法。例题一、图的遍历§1.1 深度优先搜索DFS寻找有环三色标记法原因是为了区分不同的连通块和遍历起点(有向图)。DFS适合搜索所有可能的路径但不适用于最短路问题。分类题号题目备注连通块基础547省份数量重要连通块基础1971寻找图中是否存在路径重要连通块基础841钥匙和房间重要连通块基础1319连通网络的操作次数扩展连通块基础2316统计无向图中无法互相到达点对数扩展连通块基础2492两个城市间路径的最小分数扩展连通块基础2685统计完全连通分量的数量扩展路径搜索797所有可能的路径重要路径搜索LCP 07传递信息扩展路径搜索1306跳跃游戏 III扩展DAG / 拓扑相关207课程表重要DAG / 拓扑相关802找到最终的安全状态重要DAG / 拓扑相关2192有向无环图中一个节点的所有祖先扩展图上扩散 / 传播2101引爆最多的炸弹扩展图上扩散 / 传播924尽量减少恶意软件的传播扩展并查集可替代 DFS721账户合并扩展删除3387两天自由外汇交易后的最大货币数难度偏高 / 综合技巧删除3695交换元素后的最大交替和难度偏高删除928尽量减少恶意软件的传播 II2000删除2092找出知晓秘密的所有专家2000删除3108带权图里旅途的最小代价2000删除3310移除可疑的方法题型偏综合删除261以图判树会员题删除323无向图中连通分量的数目会员题一、BFS 最短路边权为 1边权为1使用BFS最快。分类 题号 题目 备注基础单源 BFS 3243 新增道路查询后的最短距离 I 重要基础单源 BFS 1311 获取你好友已观看的视频 重要多源 / 全源 BFS 3015 按距离统计房屋对数目 I 重要状态图 BFS 1129 颜色交替的最短路径 经典 / 分层状态建图转换 815 公交路线 经典 / 超时风险低环检测 BFS 2608 图中的最短环 扩展综合模拟 2039 网络空闲的时刻 扩展会员题跳过 3807 修复边以遍历图的最小成本 会员题以下是对该题单的二次筛选结果保留最具代表性、适合进一步练习的题目一、图论建模 BFS 最短路最短路最短距离最短修改次数这种说法可以建模为图论的最短路问题转化数字的最小运算数 开锁次数转化数字的最小运算数BFS和双向BFS仅适用于有限状态数的最短路问题状态的数量等于时间复杂度状态的定义数独华容道分类 题号 题目 备注基础状态建模 433 最小基因变化 重要基础状态建模 752 打开转盘锁 重要矩阵状态 BFS 1284 转化为全零矩阵的最少反转次数 重要矩阵状态 BFS 773 滑动谜题 重要字符串状态 BFS 127 单词接龙 重要 / 建议双向 BFS字符串状态 BFS 301 删除无效的括号 经典扩展字符串状态 BFS 854 相似度为 K 的字符串 难度偏高 / 剪枝练习图论状压 847 访问所有节点的最短路径 经典 / 状态压缩跳跃游戏类 1345 跳跃游戏 IV 重要跳跃游戏类 2059 转化数字的最小运算数 重要跳跃游戏类 1654 到家的最少跳跃次数 经典 / 有界 BFS跳跃游戏类 2998 使 X 和 Y 相等的最少操作次数 扩展跳跃游戏类 3629 通过质数传送到达终点的最少跳跃次数 扩展会员题跳过 1197 进击的骑士 会员题会员题跳过 3141 最大汉明距离 会员题综合 / 较难 488 祖玛游戏 难度偏高 / 模拟复杂综合 / 较难 514 自由之路 难度偏高 / 环形 DPBFS综合 / 较难 3690 拆分合并数组 难度偏高二、拓扑排序分类 题号 题目 备注前置理解 1557 可以到达所有点的最少点数目 重要 / 理解入度为0的点基础拓扑排序 210 课程表 II 重要 / 输出拓扑序基础拓扑排序 802 找到最终的安全状态 重要 /反向图思维拓扑 建图 2115 从给定原材料中找到所有可以做出的菜 经典 / 依赖关系建模拓扑 矩阵 2392 给定条件下构造矩阵 扩展 / 行列双拓扑拓扑 贪心 310 最小高度树 经典 / 剥洋葱法拓扑 验证 1361 验证二叉树 重要 / 入度出度判定难度偏高跳过 1591 奇怪的打印机 II 2291分 / 复杂模拟难度偏高跳过 1203 项目管理 2419分 / 双层拓扑难度偏高跳过 1632 矩阵转换后的排名 2530分 / 并查集拓扑难度偏高跳过 2603 收集树中金币 2712分 / 复杂树形DP会员题跳过 444 序列重建 会员题会员题跳过 269 / LCR 114 火星词典 会员题会员题跳过 2371 最小化网格中的最大值 会员题会员题跳过 3481 应用替换 会员题三、在拓扑序上 DP选作拓扑序DP分类 题号 题目 备注基础拓扑DP 851 喧闹和富有 重要 / 刷表法入门基础拓扑DP 2050 并行课程 III 重要 / 最长路径DP进阶拓扑DP 1857 有向图中最大颜色值 经典 / 颜色计数DP会员题跳过 1136 并行课程 会员题难度偏高跳过 3620 恢复网络路径 题目信息不完整以下是对该题单的二次筛选结果保留最具代表性、难度适中、降低解法重复的题目。三、最短路§3.1 单源最短路Dijkstra 算法分类 题号 题目 备注基础入门 743 网络延迟时间 重要 / 标准模板题基础入门 3341 到达最后一个房间的最少时间 I 重要 / 网格图Dijkstra入门理解原理 3112 访问消失节点的最少时间 重要 / 理解节点失效时间设计类 2642 设计可以求最短路径的图类 重要 / Dijkstra类的设计概率类 1514 概率最大的路径 经典 / 乘积转加法网格图 1631 最小体力消耗路径 经典 / 多种解法网格图 778 水位上升的泳池中游泳 经典 / 与1631类似但不同网格图 2577 在网格图中访问一个格子的最少时间 扩展 / 时间依赖等待计数类 1976 到达目的地的方案数 经典 / 最短路计数第二短路径 2045 到达目的地的第二短时间 经典 / BFS也可K站中转 787 K站中转内最便宜的航班 经典 / 与1928类似选更经典的动态规划 1928 规定时间内到达终点的最小花费 扩展 / DPDijkstra赛车 818 赛车 难度偏高 / 状态图BFSDP分层图 LCP 35 电动车游城市 经典 / 分层图入门SPFA/差分约束 2589 完成所有任务的最少时间 扩展 / 差分约束§3.2 全源最短路Floyd 算法Floyd 算法本质是三维 DP。理解 DP 一定要基于空间优化前的写法。转换字符串的最小成本这题不能用BFS来做状态空间很大。不过可以抽象为最短路来做先单独求解每一个字符转换的最小成本。因为有多个字符所以使用多源最短路算法。–2642. 设计可以求最短路径的图类 1811 动态加边1334. 阈值距离内邻居最少的城市 18552976. 转换字符串的最小成本 I 18822959. 关闭分部的可行集合数目 20772977. 转换字符串的最小成本 II 2696四、最小生成树涉及到 Kruskal 算法和 Prim 算法。前者一般用于稀疏图后者一般用于稠密图。一般使用堆优化的Krusal算法。最小带权和的生成树。–1584. 连接所有点的最小费用 18583600. 升级后最大生成树稳定性 2301 做法不止一种二分Krusal算法1489. 找到最小生成树里的关键边和伪关键边 25721135. 最低成本连通所有城市会员题1168. 水资源分配优化会员题七、二分图染色二分图两个节点连边。典型例题分组织问题。模板交替染色法785. 判断二分图 1625786. 可能的二分法 1795787. 最大划分因子 2135只保留有用的边二分
