graph.md

2.8 图

相关题目

图的深度优先搜索

题号	标题	题解	标签	难度	力扣
797	所有可能的路径		深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
200	岛屿数量	[✓]	深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
695	岛屿的最大面积	[✓]	深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
133	克隆图	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
494	目标和	[✓]	数组 动态规划 回溯	🟠	🀄️ 🔗
144	二叉树的前序遍历	[✓]	栈 树 深度优先搜索 1+	🟢	🀄️ 🔗
94	二叉树的中序遍历	[✓]	栈 树 深度优先搜索 1+	🟢	🀄️ 🔗
145	二叉树的后序遍历	[✓]	栈 树 深度优先搜索 1+	🟢	🀄️ 🔗
589	N 叉树的前序遍历	[✓]	栈 树 深度优先搜索	🟢	🀄️ 🔗
590	N 叉树的后序遍历	[✓]	栈 树 深度优先搜索	🟢	🀄️ 🔗
124	二叉树中的最大路径和	[✓]	树 深度优先搜索 动态规划 1+	🔴	🀄️ 🔗
199	二叉树的右视图	[✓]	树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
543	二叉树的直径	[✓]	树 深度优先搜索 二叉树	🟢	🀄️ 🔗
662	二叉树最大宽度	[✓]	树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
958	二叉树的完全性检验	[✓]	树 广度优先搜索 二叉树	🟠	🀄️ 🔗
572	另一棵树的子树	[✓]	树 深度优先搜索 二叉树 2+	🟢	🀄️ 🔗
100	相同的树	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
111	二叉树的最小深度	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
841	钥匙和房间	[✓]	深度优先搜索 广度优先搜索 图	🟠	🀄️ 🔗
129	求根节点到叶节点数字之和	[✓]	树 深度优先搜索 二叉树	🟠	🀄️ 🔗
323	无向图中连通分量的数目 🔒		深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
684	冗余连接	[✓]	深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
802	找到最终的安全状态	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
785	判断二分图		深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
886	可能的二分法		深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
130	被围绕的区域	[✓]	深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
417	太平洋大西洋水流问题	[✓]	深度优先搜索 广度优先搜索 数组 1+	🟠	🀄️ 🔗
1020	飞地的数量		深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
1254	统计封闭岛屿的数目		深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
1034	边界着色		深度优先搜索 广度优先搜索 数组 1+	🟠	🀄️ 🔗
剑指 Offer 13	机器人的运动范围	[✓]	深度优先搜索 广度优先搜索 动态规划	🟠	🀄️
529	扫雷游戏		深度优先搜索 广度优先搜索 数组 1+	🟠	🀄️ 🔗

图的广度优先搜索

题号	标题	题解	标签	难度	力扣
797	所有可能的路径		深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
286	墙与门 🔒		广度优先搜索 数组 矩阵	🟠	🀄️ 🔗
200	岛屿数量	[✓]	深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
752	打开转盘锁		广度优先搜索 数组 哈希表 1+	🟠	🀄️ 🔗
279	完全平方数	[✓]	广度优先搜索 数学 动态规划	🟠	🀄️ 🔗
133	克隆图	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
733	图像渲染	[✓]	深度优先搜索 广度优先搜索 数组 1+	🟢	🀄️ 🔗
542	01 矩阵		广度优先搜索 数组 动态规划 1+	🟠	🀄️ 🔗
322	零钱兑换	[✓]	广度优先搜索 数组 动态规划	🟠	🀄️ 🔗
323	无向图中连通分量的数目 🔒		深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗
剑指 Offer 13	机器人的运动范围	[✓]	深度优先搜索 广度优先搜索 动态规划	🟠	🀄️
199	二叉树的右视图	[✓]	树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
662	二叉树最大宽度	[✓]	树 深度优先搜索 广度优先搜索 1+	🟠	🀄️ 🔗
958	二叉树的完全性检验	[✓]	树 广度优先搜索 二叉树	🟠	🀄️ 🔗
572	另一棵树的子树	[✓]	树 深度优先搜索 二叉树 2+	🟢	🀄️ 🔗
100	相同的树	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
111	二叉树的最小深度	[✓]	树 深度优先搜索 广度优先搜索 1+	🟢	🀄️ 🔗
剑指 Offer 32-III	从上到下打印二叉树 III	[✓]	树 广度优先搜索 二叉树	🟠	🀄️

图的拓扑排序

题号	标题	题解	标签	难度	力扣
207	课程表	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
210	课程表 II	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
1136	并行课程 🔒		图 拓扑排序	🟠	🀄️ 🔗
2050	并行课程 III		图 拓扑排序 数组 1+	🔴	🀄️ 🔗
802	找到最终的安全状态	[✓]	深度优先搜索 广度优先搜索 图 1+	🟠	🀄️ 🔗
851	喧闹和富有		深度优先搜索 图 拓扑排序 1+	🟠	🀄️ 🔗

图的最小生成树

题号	标题	题解	标签	难度	力扣
1584	连接所有点的最小费用		并查集 图 数组 1+	🟠	🀄️ 🔗
1631	最小体力消耗路径		深度优先搜索 广度优先搜索 并查集 4+	🟠	🀄️ 🔗
778	水位上升的泳池中游泳		深度优先搜索 广度优先搜索 并查集 4+	🔴	🀄️ 🔗

单源最短路径

题号	标题	题解	标签	难度	力扣
407	接雨水 II	[✓]	广度优先搜索 数组 矩阵 1+	🔴	🀄️ 🔗
743	网络延迟时间		深度优先搜索 广度优先搜索 图 2+	🟠	🀄️ 🔗
787	K 站中转内最便宜的航班		深度优先搜索 广度优先搜索 图 3+	🟠	🀄️ 🔗
1631	最小体力消耗路径		深度优先搜索 广度优先搜索 并查集 4+	🟠	🀄️ 🔗
1786	从第一个节点出发到最后一个节点的受限路径数		图 拓扑排序 动态规划 2+	🟠	🀄️ 🔗

多源最短路径

题号	标题	题解	标签	难度	力扣
815	公交路线		广度优先搜索 数组 哈希表	🔴	🀄️ 🔗
1162	地图分析		广度优先搜索 数组 动态规划 1+	🟠	🀄️ 🔗

次短路径

题号	标题	题解	标签	难度	力扣
2045	到达目的地的第二短时间		广度优先搜索 图 最短路	🔴	🀄️ 🔗

差分约束系统

题号	标题	题解	标签	难度	力扣
995	K 连续位的最小翻转次数		位运算 队列 数组 2+	🔴	🀄️ 🔗
1109	航班预订统计		数组 前缀和	🟠	🀄️ 🔗

二分图基础题目

题号	标题	题解	标签	难度	力扣
785	判断二分图		深度优先搜索 广度优先搜索 并查集 1+	🟠	🀄️ 🔗

二分图最大匹配

题号	标题	题解	标签	难度	力扣
LCP 04	覆盖		位运算 图 数组 2+	🔴	🀄️
1947	最大兼容性评分和		位运算 数组 动态规划 2+	🟠	🀄️ 🔗
1595	连通两组点的最小成本		位运算 数组 动态规划 2+	🔴	🀄️ 🔗