Graph

大类

• 有向图
• 无向图
• 加权图

有向图

考虑入度和出度。

• 841. 钥匙和房间
• 997. 找到小镇的法官
• 1557. 可以到达所有点的最少点数目

拓扑排序

• 207. 课程表

• 210. 课程表 II

• 851. 喧闹和富有

• 802. 找到最终的安全状态

• 310. 最小高度树

• 444. 序列重建

• 1557. Minimum Number of Vertices to Reach All Nodes

最小生成树

Prim Kruskal 都是考虑权值最小的边，但角度有所不同

Prim	Kruskal
从点出发，考虑当前最近的点	从边出发，考虑所有边中cost最小的边。

Prim

• 1135. 最低成本联通所有城市

Kruskal

• 1631. 最小体力消耗路径
• 778. 水位上升的泳池中游泳

最短路径问题

模板题：743. 网络延迟时间

n 为顶点个数， E为边个数

图	单源\多源	负权边	负权环	时间复杂度	空间
Dijkstra	单源	不适用	不适用	$O(n^2 + E)$	$O(n^2)$
Dijkstra（堆优化）	单源	不适用	不适用	$O(n + E\log{E})$	$O(n + E)$
Bellman-Ford	单源	适用	适用	$O(nE)$	$O(E)$
SPFA（栈\队列优化）	单源	适用	适用	$O(k*E)$	$O(E)$
Floyd	多源	适用	不适用	$O(n^3)$	$O(n^2)$
A star

Dijkstra

每次选取距离起点最近的点，选取之后更新各点的最短距离。

Dijkstra不适用于负权边,因为不考虑已经走过的地方。

优化：最小堆

堆优化Dijkstra

用priority_queue<>存储边， $O(\log(n)$时间内获取最小权边

• 2045. 到达目的地的第二短时间
• 1786. 从第一个节点出发到最后一个节点的受限路径数

相关参数

• priority_queue<> minHeap 存边和点，每次取权值最小的边。
• dist[n] 最短路径
• 起点start, 终点target

实现思路

• dist[start] = 0,同时minHeap 入队起点，边权值设为0

易错点

• 注意设置每次更新dist[i]都要将dist[i]和i入队，因为可能比minHeap中该点（但该点未visited）的dist要更小。

题外话

Dijkstra(堆优化)跟Prim算法很像，都是取dist最小的边。

区别在于， 前者的dist是最短距离，后者存的是一条边的权重。

因为Prim是把已经成树的点看作一个整体，只要看一条边的权重即可。

扩展

• 1162. 地图分析 多源最短路。二维表

Bellman-Ford

遍历边来relax，对于不含负权环的图来说，遍历n-1次一定能设置好最短路径。

适用负权环

• 1334. 阈值距离内邻居最少的城市
• 787. K 站中转内最便宜的航班
• 1129. Shortest Path with Alternating Colors

检测负环

1. 只需对第n次检查是否relax了dist数组就能判断是否含负权环。

Bellman-Ford优化：SPFA

DFS(Stack) / BFS (Queue)

建议使用BFS(Queue)优化的SPFA, 无负环时不影响效率。

实现思路

• bool inQueue[]表示点是否在Q里头
• dist[]距离
• 将起点入队，同时inQueue[start] = true
• 取队首元素为cur，同时设置inQueue[cur] = false
• 更新与cur相邻的dist[]，如果邻点inQueue[] = false， 则将其入队，且设置inQueue[] = true， 一入队就更新inQueue防止重复入队。
• 重复上述步骤，直至Q.empty == true，至此dist数组更新完毕。

检测负环

1. 用一个cnt[]来记录入队次数，如果入队次数大于n，就说明有负环。
2. 用一个cnt[]来记录从起点到i的最短距离包含点的个数， 初始化cnt[] = 1, 用点u松弛v时更新cnt[v] = cnt[u] + 1 ， 若发现cnt[v] > n则存在负环

Floyd

基于DP，因此K放外层循环。

对于i，j两点。用k点检查是否缩短该两点距离

Floyd适用负权边，因为三重循环，一直寻找最短。

Dijkstra、Bellman-Ford都不适用负权环。

总结

• 注意判断是否是有向图。

• 注意有限制的最短路，不同的方法，不同优化对应不同场景。

  • 当权值为非负时，用Dijkstra。
  • 可能有负权环，用BFS-Bellman-Ford，cnt[]检测入队次数。

• Bellman_Ford 可解决有中转次数的最短路问题。

• Floyd 适用于经过的所有点编号不会超过k的问题。最小环或者求“重心点”（即删除该点后，最短路值会变大）。

深度优先搜索

常辅以记忆化递归（memo）

对于图，一般需要一个visited数组来防止重复递归。如果图的元素限制了递归，就可能不需要。

对于需要返回值来提前结束递归或者积累子问题的结果，我们需要设置返回值，其他一般为void，获取全部可能。

回溯问题一般在函数前面部分处理递归出口，其他一般在循环中判断是否进入递归，这样更具有自由度：一个返回值所含信息有限，无法处理所有情况。实际上，返回值和递归入口出口的设置很灵活，难以总结。

树的DFS中，只能向下。但如果有parent数组记录，则可向上，但DFS时需要多一个from参数防止重复递归。

• 200. 岛屿数量

• LCP 07. 传递信息

• 863. 二叉树中所有距离为 K 的结点

• 62. 不同路径

• 63. 不同路径 II

• 980. 不同路径 III

返回值做子问题的累计

• 329. 矩阵中的最长递增路径
• 2049. 统计最高分的节点数目

返回值做提前结束递归

• 403. 青蛙过河
• 785. 判断二分图

返回值告知整体情况

这种情况，在循环内限制递归入口不能实现理想效果或实现复杂。

• 1020. 飞地的数量

循环内限制递归入口

• 1034. 边界着色

广度优先搜索

注意最大、最小次数、最短距离等字眼，可以考虑BFS。

大致思路

相关参数

• visited防止重复搜索。如果是有向图，就可以不用。
• queue 用于存储待搜索的节点
• dirs搜索方向，level搜索深度,size每一层搜索的节点个数。

实现

• 将当前状态入队，根据搜索规则将下一轮的状态入队。queue 不一定是队列，只要是存现在的状态就行，如哈希表。
• visited的具体实现可以是数组，也可以是哈希表。
• 队空搜索完成。

易错

不同于Prim和priority_queue Dijkstra， BFS是加入queue时就设置visited，防止重复入queue。

• 130. 被围绕的区域

• 200. 岛屿数量

• 547. 省份数量

• 1091. 二进制矩阵中的最短路径

• 1020. 飞地的数量

• 1034. 边界着色

• 2039. 网络空闲的时刻

• 909. 蛇梯棋

• 433. 最小基因变化

• 994. 腐烂的橘子 多源BFS

• 417. Pacific Atlantic Water Flow 多次BFS

• 1765. 地图中的最高点 (多源BFS) DP

• 1162. 地图分析 （多源BFS）

• 752. 打开转盘锁 (哈希visited)

• 301. 删除无效的括号

• 773. 滑动谜题

01 BFS

• 2290. 到达角落需要移除障碍物的最小数目

扩展

双向BFS

有限次数BFS

• 2059. 转化数字的最小运算数

• 127. 单词接龙

• 1345. 跳跃游戏 IV

  由于BFS搜索的状态增加是指数级别的，条件允许可以考虑双向BFS。

• 1036. 逃离大迷宫

  数据量很大，考虑有限次数的BFS。

• 815. 公交路线

并查集 Disjoint-set structure

将二维下标转化为一维下的通常需要 index = i * col + j转化

• 547. 省份数量
• 200. 岛屿数量
• 130. 被围绕的区域
• 685. 冗余连接 II
• 778. 水位上升的泳池中游泳
• 399. 除法求值
• 785. Is Graph Bipartite?
• 886. Possible Bipartition

其他

不好分类

• 407. 接雨水 II
• 399. 除法求值