前言

本篇介绍算法竞赛中最最重点的一个部分搜索和图论。搜索分为广度优先搜索和深度优先搜索，在题目中非常的常见。而在图论中经常考察的最短路与最小生成树，是算法中极为重要一项基本功。

DFS(暴搜)

可以被称为“2022年度算法”的一款算法，实用价值极高！！！

DFS（深度优先搜索）本质上维护一个隐藏的stack，不具有最短性

空间：$O(h)$ （较节省空间）

DFS涉及两个重要的概念：

• 回溯：按代码理解就是需要return的地方
• 剪枝：提前判断一些肯定不满足条件的方法，并将其直接回溯

注意点：

• 回溯的过程中注意恢复现场
• 必然有一个标记访问的过程

全排列数字

将1-n之间的数字全排序

#include <iostream>
using namespace std;const int N = 10;
int n;int path[N];
bool st[N];// u理解为树的层
void dfs(int u) {if (u == n) {for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);puts("");return;}// 枚举1~nfor (int i = 1; i <= n; i ++ ) {if (!st[i]) {path[u] = i;st[i] = true;dfs(u+1);st[i] = false;}}
}int main() {scanf("%d", &n);dfs(0);return 0;
}

n-皇后

逐行搜

通过分析题目给出的规则，发现每一行只能出现一个皇后。加上列与对角线的限制，暴搜出所有满足题目的答案

dfs记录行数, 时间复杂度$O(n\ast n!)$

#include <iostream>
using namespace std;const int N = 10;
int n;
char str[N][N];
// 分别记录列、对角线、反对角线
bool col[N], dg[N], udg[N];// u为行数
void dfs(int u) {if (u == n) {for (int i = 0; i < n; i ++ ) puts(str[i]);puts("");return;}for (int i = 0; i < n; i ++ ) {// y = x + b -> b = y - x// y = -x + b -> b = y + xif (!col[i] && !dg[i-u+n] && !udg[i+u]) {str[u][i] = 'Q';col[i] = true, dg[i-u+n] = true, udg[i+u] = true; //标记dfs(u+1);col[i] = false, dg[i-u+n] = false, udg[i+u] = false; //还原str[u][i] = '.';}}
}int main()
{scanf("%d", &n);for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ )str[i][j] = '.';dfs(0);return 0;
}

逐格搜

dfs同时记录行数，列数，与皇后数， 时间复杂度$O(2^{n^2})$

每一格仅有两种情况即有皇后和无皇后

#include <iostream>
using namespace std;const int N = 10;
int n;
char str[N][N];
bool row[N], col[N], dg[N], udg[N];void dfs(int x, int y, int s) {// 走到一行的末尾，自动定位至下一行行头if (y == n) y = 0, x++;if (x == n) {if (s == n) {for (int i = 0; i < n; i ++ ) puts(str[i]);puts("");}return;}// 此格无皇后dfs(x, y + 1, s);// 此格有皇后if (!row[x] && !col[y] && !dg[y-x+n] && !udg[y+x]) {str[x][y] = 'Q';row[x] = true, col[y] = true, dg[y-x+n] = true, udg[y+x] = true;dfs(x, y + 1, s + 1);row[x] = false, col[y] = false, dg[y-x+n] = false, udg[y+x] = false;str[x][y] = '.';}}int main() {scanf("%d", &n);for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )str[i][j] = '.';dfs(0, 0, 0);return 0;
}

BFS

BFS（广度优先搜索）本质上维护一个queue，能够计算最短路

空间：$O(2^h)$ （所需要的空间和指数呈指数级别）

BFS记录路径

开辟一个数组，记录每一个点是由哪个点转移而来

但最后输出的结果为倒序

BFS之冲出迷宫

这道除了用到了BFS外，还有两处之前没有掌握的地方

1. 距离的记录：运用DP动态规划，记录下每一层点到起点的距离
2. 路径过程的记录：用一个数组记录当前点的前一个点

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y secondusing namespace std;const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N]; // 记录图
int d[N][N]; // 记录距离的同时标记此点是否已访问
PII q[N*N], path[N][N]; // 模拟队列，记录过程路径
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};int dfs() {int hh = 0, tt = -1;q[++tt] = {1, 1};memset(d, -1, sizeof d); // 初始化为-1d[1][1] = 0;while (hh <= tt) {auto t = q[hh++];for (int i = 0; i < 4; i++) {int x = t.x + dx[i], y = t.y + dy[i];if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == 0 && d[x][y] == -1) {d[x][y] = d[t.x][t.y] + 1; // *DP记录下每一层的距离path[x][y] = t; // *记录下当前点的下一个点q[++tt] = {x, y};}}}return d[n][m];
}int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j++)scanf("%d", &g[i][j]);cout << dfs() << endl;// 反向遍历，得到起点到终点的路径int a = n, b = m;while (a >= 1 || b >= 1) {cout << a << ' ' << b << endl;auto t = path[a][b];a = t.first, b = t.second;}return 0;
}

树与图

树可以被看作一种特殊的图（只有一个根结点）

图的存储方式分别两种：

• 邻接矩阵：二维数组记录ab ba（无向图同时记录双向），无权重用0-1表示，有权重则记录对应的权重值

• 邻接表：如下

另，当题目中的数据超过$10^6$时，考虑用scanf, printf，以下则不限

邻接表存储

数组模拟邻接表

图中的每个结点都有一个单链表，用于存储该点可以到达的点

// h[]代表存储了多个结点，与单链表中的head比较记忆
int h[N], e[M], ne[M], idx;memset(h, -1, sizeof h);void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

遍历

DFS

bool st[N];void dfs(int u) {st[u] = true; // 标记该点已被访问// 遍历该点的邻接点for(int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (!st[j]) dfs(j);}
}

树的重心

难理解

首先这是比较绕的一道题，可能是我看了这么多算法以来，花了最多时间的一道

不过我大抵碰到了我的一个软肋，树+DFS。不容易理解的一个数据结构加上不易理解的一个算法，而恰恰这样题总是能够以很少的代码，解决很复杂的题

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 1e5 + 10, M = 2*N;
int n;
bool st[N];
int h[N], e[M], ne[M], idx;
int ans = N;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}// 返回以u为根结点子树的结点个数
int dfs(int u) {st[u] = true;// sum:存储 以u为根的树 的节点数，包括u// res:存储 删掉某个节点之后，最大的连通子图节点数int sum = 1, res = 0;for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (!st[j]) {int s = dfs(j); // 返回以j为根结点的子树中的结点数，包括其本身res = max(res, s); // 比较u结点的每个子树大小，取最大sum += s; //计算u结点以下所有子树结点之和，包括u本身}}res = max(res, n - sum); // 最大的子树与u结点以上部分作比取最大值ans = min(ans, res); // 比较得出最大值中的最小值，即为重心return sum;
}int main() {scanf("%d", &n);memset(h, -1, sizeof h);for(int i = 0; i < n-1; i++) {int a, b;scanf("%d%d", &a, &b);add(a, b), add(b, a);}dfs(1);cout << ans << endl;return 0;
}

BFS

在权重为1的情况下，可以用BFS求解最短距离

queue<int> q;
int d[N]; // 存储距离memset(h, -1, sizeof h);
int dfs() {q.push(1);memset(d, -1, sizeof d);d[1] = 0;while (q.size()) {int t = q.front();q.pop();for(int i = h[t]; i != -1; i = ne[i]) {if (d[i] == -1) {d[i] = d[t] + 1;q.push(i);}}}return d[n];
}

拓扑排序

若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列

如上图，0->1->2->3->4即为拓扑序列。注意拓扑序列并不唯一

时间复杂度：$O(n+e)$，$n$ 表示点数，$e$ 表示边数

搜索入度为零的顶点所需的时间是$O(n)$，每个顶点入度减1的运算共执行了$e$次，由此得出时间复杂度

• 有向图才存在拓扑序列
• 利用BFS实现拓扑排序

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N]; // d[]存储每个点的入度void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}// 核心代码
// 简言之，入度为0就入队，队列的次序即为拓扑序列
bool topsort() {int hh = 0, tt = -1;for(int i = 1; i <= n; i++)if (!d[i]) q[++tt] = i; // 找到入度为0的突破口while (hh <= tt) {int t = q[hh++];// 遍历并修改入度for(int i = h[t]; i != -1; i = ne[i]) {int j = e[i];d[j]--;if (d[j] == 0) q[++tt] = j;}}// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列return tt == n-1;
}int main() {scanf("%d%d", &n, &m);memset(h, -1, sizeof h);for(int i = 0; i < m; i++) {int a, b;scanf("%d%d", &a, &b);add(a, b);d[b]++; // 入度+1}if (topsort()) {// 入队的顺序就是拓扑序for(int i = 0; i < n; i++) printf("%d ", q[i]);puts("");} else puts("-1");return 0;
}

最短路问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-msayevvn-1644164714324)(最短路.png)]

单源最短路

从某一点到图上所有点的最短距离

朴素版Dijkstra

边权均为正，体现贪心的思想

时间复杂度：$O(n^2+m)$，n个点m条边

适用于稠密图（$m$与$n^2$是一个数量级），使用邻接矩阵存储

int g[N][N];
int dist[N];
bool st[N];memset(g, 0x3f, sizeof g);int dijkstra() {// 初始化距离为正无穷！！memset(dist, 0x3f, sizeof dist);dist[1] = 0;/* 有几个点就有几轮循环* 每轮选择距离最近的点，去更新其它点* 重复n次，就能使得每一个点都被选取到  */for(int i = 0; i < n; i++) {// 遍历选出当前没被访问过，且距离原点最近的点int t = -1;for(int j = 1; j <= n; j++)if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;st[t] = true; // 标记访问// 用这个距离最近的点，去更新其它的点距离原点的距离for(int j = 1; j <= n; j++) dist[j] = min(dist[j], dist[t] + g[t][j]);}// 判断是否可以到达目标点if (dist[n] == 0x3f3f3f3f) return -1;else return dist[n];
}

堆优化版Dijkstra

边权均为正

时间复杂度：$O(mlogn)$，n点m边

适用于稀疏图

Bellman-Ford算法

存在负边

时间复杂度：$O(nm)$

SPFA算法

存在负边，(队列优化的Bellman-Ford算法)

时间复杂度：$O(m)$，最坏情况为$O(nm)$

判负环

多源汇最短路

计算任意一点到任意一点的最短距离

Floyd算法

时间复杂度：$O(n^3)$

最小生成树

二分图

染色法

匈牙利算法

参考资料

AcWing算法基础课