算法备忘录·搜索与图论
本文最后更新于 2024年5月15日 凌晨
一直以来,没能系统学习算法,是我心中的痛;现在学了 y 总的算法基础课,做做笔记,希望能够有所收获。
这是第四节,搜索与图论。
搜索与图论
图的搜索
搜索 | 数据结构 | 空间 | 优劣 |
---|---|---|---|
DFS | stack | O(h) | 不具有最短性 |
BFS | queue | O(2^h) | “最短路” |
DFS
- 顺序——搜索树
- 递归(系统帮我们维护了栈)—— 回溯(从递归出来后还原现场)
- 剪枝:递归过程中能够直接判断然后回溯
- 递归(系统帮我们维护了栈)—— 回溯(从递归出来后还原现场)
- 一般无通用框架,关键是搜索的顺序
BFS
能够搜索到最短(边的权重为 1)
有通用的框架
1
2
3
4
5queue ← 初始状态
while (queue 不空){
t ← 队头
扩展队头
}
图的存储
- 有向图、无向图(无向图就当作双向有向图)
邻接矩阵
g[a][b]
存储边 a->b
邻接表
每个点有一个单链表,类似于拉链法
使用的邻接表的 TLE 极可能是没有初始化
h[]
模板
1
2
3
4
5
6
7
8
9
10
11// 对每个节点 k,开单链表,存储其能够走到的所有点。h[k] 存储单链表的头节点
int h[N], e[N], ne[N], idx;
//添加一条边 a -> b
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
图的遍历
- 时间复杂度为 , 表示点数, 表示边数
深度优先遍历
遍历不需要恢复现场
模板
1
2
3
4
5
6
7
8int dfs(int u){
st[u] == true; // st[u] 表示点 u 已经被遍历过
for (int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if (!st[j]) dfs(j); //不需要恢复现场
}
}
宽度优先遍历
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17queue<int> q;
st[1];
q.push(1);
while(q.size()){
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if (!st[j]){
st[j] = true; // 表示点 j 已经被遍历过
q.push(j);
}
}
}
有向图的拓扑序列
宽度优先搜索的应用
拓扑序列:所有的边都是从前指向后的
- 有向无环图一定存在拓扑序列——所以有向无环图称为拓扑图
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22bool tosort(){
int hh = 0, tt = -1;
// d[i] 存储点的入度
for (int i = 1; i <= n; i ++ ){
if (!d[i])
q[++ tt] = i; // 加入所有入度为 0 的点
}
while (hh <= tt){
int t = q[hh ++];
// 对于队头 t,遍历其子节点,将子节点每个入度 - 1,如果入度为 0 则入队。
for (int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if (--d[j] == 0)
q[++ tt] = j;
}
}
//如果所有点都入队了,说明存在拓扑序列;
return tt = n - 1;
}
最短路
图论最难的部分是实现
- 图中有 个点、 条边
graph LR
A[最短路] -->B[单源最短路]
A --> C[多源汇最短路]
B --> D[所有边权都是正数]
B --> E[存在负权边]
D --> F[朴素 Dijstra 算法]
D --> G[堆优化版的 Dijstra 算法]
E --> H[Bellman-Ford]
E --> I[SPFA]
C --> J[Floyd 算法]
Dijkstra 算法
朴素 Dijkstra 算法
时间复杂度
思路
- dist[1] = 0, dist[i] = + INF;
- for i in 1 ~ n:
t ← 不在 s 中的、距离最近的点(s 是当前已确定最短距离的点);
s ← t;
用 t 更新其它点(1 ~ n)到起点的距离; - 执行 2 操作 n 次
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27int g[N][N]; // 存储每条边
int dist[N]; // 存储 1 号点到每个点的距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求 1 号点到 n 号点的最短路,若不存在则返回 -1
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i <n - 1; i ++ ){
int t = -1;
// 在未确定最短路的点中,寻找距离最小的点 t
for (int j = 1; j <= n; j ++ )
if (!st[j] &&(t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
// 用 t 更新其他点的距离
for (int j = 1; j <= n; j ++ ){
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
堆优化版 Dijkstra
我们发现,朴素 Dijkstra 每次需要寻找未确定最短路的点中距离最小的点,那么我们可以用小根堆来维护这个最小值点
时间复杂度 ,适合稀疏图
使用邻接表存储,是为了快速找到从每个点出发的所有邻边
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储
int dist[N]; // 存储 1 号点到每个点的距离
bool st[N]; // 存储每个点的最短路是否已经确定
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first 存储距离,second 存储节点编号
// 队列为空时,即没有点更新距离
while (heap.size()){
// 相比于朴素版,这里直接取了堆顶
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]){
int j = e[i];
if (dist[j] > distance + w[i]){
dist[j] = distance + w[i];
heap.push({dist[j], j}); // 将更新了距离的点放入队列
}
}
}
}
Bellman-Ford 算法
时间复杂度 ,其中 表示点数, 表示边数
因为有负权边,因此每个点都需要对每个边进行遍历,从而更新
dist[]
如果第 次迭代仍然会松弛三角不等式,就说明存在一条长度是 的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路
注意最后的
dist[n] > 0x3f3f3f3f / 2
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23int n, m;
int dist[N];
struct Edge{
int a, b, w;
}edges[M]; // 边,a表示出点,b表示入点,w表示边的权重
// 求 1 号点到 n 号点的最短路,若不存在则返回 -1
int bellman_ford(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n; i ++ ){
for (int j = 0; j < m; j ++ ){
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], dist[a] + w);
}
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1; // 因为有负权边,所以即便是没有通路 dist[n] 也有可能减少了一些
return dist[n];
spfa 算法
队列优化的 Bellman-Ford 算法。仅更新队列中的点,这样就加快了速度。但是如果存在闭环,队列会不断更新从而不断循环。
- 因此,判断负环的方法是引入
cnt[]
,记录每个点最短距离更新的次数
- 因此,判断负环的方法是引入
时间复杂度平均 ,最坏情况下 。因此时间不是很紧的题可以用 spfa 代替 Dijkstra。
为什么 spfa 最后说可以用
dist[n]==0x3f3f3f3f
进行判断?这是因为,Bellman-ford 在更新时,即便是没有通路从 1 到 n,但是与 n 相连的点 n - 1 也会让dist[n]
更新;而 spfa 的话,如果没有连接有通路,那么 n - 1 是不会进入队列被更新到。因此dist[n]
不会变化。模板
- spfa 求 1 到 n 的最短路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 用邻接表存储所有边
int dist[N]; // 存储 1 号点到每个点的距离
bool st[N]; // 存储点是否在队列中
int spfa(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size()){
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[i]; i != -1; i = ne[i]){
int j = e[i];
if (dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
if (!st[j]){ // 如果队列中已存在 j,则不需要将 j 重复插入
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}- 判断图中是否存在负环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35int n;
int h[N], w[N], e[N], ne[N], idx;
int dist[N], cnt[N];
bool st[N];
bool spfa(){
queue<int> q;
// 负环不一定要从点 1 出发,因此把所有点放入队列中
for (int i = 1; i <= n; i ++ ){
q.push(i);
st[i] = true;
}
while (q.size()){
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]){
int j =e[i];
if (dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] > n) return true; // 说明最短路中至少含了 n + 1 个点
if (!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
FLoyd 算法
- 时间复杂度是
- Floyd 算法极其简洁,但是难以理解,因为是用了 DP 思想:核心是公式 。在计算 时,需要依赖于 ,所以 $k4 应该先被算出来。
一个笑话:为什么 Dijkstra 不能提出 floyd 算法?因为他的名字是 ijk 而不是 kij。
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// 初始化
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <= n; j ++ ){
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
}
}
// Floyd 算法结束后,d[a][b] 表示 a 到 b 的最短距离
void floyd(){
for (int k = 1; k <= n; k ++ ){
for (int i = 1; i <= n; i ++ ){
for (int j = 1; j <= n; j ++ ){
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
最小生成树
graph LR
A[最小生成树] -->B[Prim 算法]
A --> C[Kruskal 算法]
B --> D[朴素 Prim 算法]
B --> E[堆优化版的 Prim 算法]
Prim 算法
朴素 Prim 算法
适用于稠密图
时间复杂度是
思路
- dist[i] = + INF;
- for i in 1 ~ n:
t ← 不在 s 中的、距离最近的点(s 是当前已确定最短距离的点);
s ← t;
用 t 更新其它点(1 ~ n)到集合的距离;(点到集合的距离:点所有连到集合的边的最小距离) - 执行 2 操作 n 次
模板
1 |
|
堆优化版的 Prim 算法
- 适用于稀疏图【不常用,因为不好写】
- 时间复杂度是
Kruskal 算法
- 适用于稀疏图
- 时间复杂度是
- 思路
- 按所有边按权重从小到大排序(瓶颈 )
- 枚举每条边 ab(权重为 c),如果 a、b 不连通,将这条边加入集合中
- 模板
1 |
|
二分图
染色法
- 时间复杂度
- 用于判断一个图是不是二分图
- 二分图:图中不含奇数环
- 思路
for i in 1 ~ n:
if i 未染色:
dfs(i, 1) - 模板
1 |
|
匈牙利算法
时间复杂度 ,实际运行时间远小于
用于求二分图的最大匹配
思路
- 遍历第一个集合的点,找与其可以匹配的点。可以匹配的点满足这样的规则:
- 如果这个点没有被匹配,那么它俩匹配
- 如果这个点被匹配过了,那么考虑与它之前匹配的点能否匹配其它的点。如果可以,那么这个点与新点匹配;否则不可以匹配。
- 遍历第一个集合的点,找与其可以匹配的点。可以匹配的点满足这样的规则:
模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25int n1, n2; // n1 表示集合 1 中的点数,n2 表示集合 2 中的点数
int h[N], e[M], ne[M], idx; // 匈牙利算法中只会用到从第一个集合指向第二个集合的边,所以这里只用存一个方向的边
int match[M]; // 存储集合 2 中每个点当前匹配集合 1 中对应的点
bool st[N]; // 表示集合 2 中的点是否被遍历过,为了避免 find(x) 做深搜无限循环
bool find(int x){
for (int i = h[x]; i != -1; i = ne[i]){
int j = e[i];
if (!st[j]){
st[j] = true;
if (match[j] = 0 || find(match([j]))){
match[j] = x;
return true;
}
}
}
return false;
}
// 求最大匹配数,依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ ){
memset(st, false, sizeof st); // 每次都要刷新 st[]
if (find(i)) res ++;
}
算法备忘录系列目录:
第一节 算法备忘录·基础算法
第二节 算法备忘录·数据结构
第三节 算法备忘录·杂项
第四节 算法备忘录·搜索与图论
第五节 算法备忘录·数学知识
第六节 算法备忘录·动态规划
第七节 算法备忘录·贪心
第八节 算法备忘录·时空复杂度分析
第九节 算法备忘录·杂项