第三章：搜索与图论，本章的主要内容是dfs（深度优先搜索），bfs（广度优先搜索），图的存储和表示，以及对图的遍历，最短路算法等。
1.搜索
搜索分为宽度优先搜索（dfs）和广度优先搜索（bfs）。这两种搜索都可以遍历所有的空间，区别在于遍历的方式不同。一般在算法题中所有可能的情况是一个树，而搜索算法的就是对这个树的遍历。
dfs
深度优先搜索，顾名思义，优先向更深的方向搜索，当搜索到叶子节点无路可走的时候，便会回退到父节点，查看父节点是否还有没有遍历到的子节点，如果有则继续遍历，如果没有则继续向上回退，这个过程称为回溯。在回溯之后最重要的一步是恢复现场，即将从该节点向后的搜索产生的影响恢复，保证从同一节点出发不管向哪条路径探索，看到的状态都是一样的。
在有些时候，不需要搜索到叶子节点我们便可以确定不需要向下搜索了，此时便可以直接回溯，这称为剪枝。顾名思义，就是剪去搜索树中从当前节点向下的树枝。剪枝一般分为两种，一种是最优性剪枝，当我们可以确定当前情况不是全局最优解时，我们便可以不再继续向下搜索了，直接回溯；另一种方式是我们已经发现当前情况不合法了，也可以直接回溯。
一般来说搜索都是一种思想，不同的题目代码差别会比较大，没有固定的模板，这里放几道dfs的例题：全排列， 选数，八皇后，01迷宫，会议。
1
/ \
/ \
2 7
/ \ \
3 6 8
/ \
4 5
对于如上搜索树，dfs的遍历顺序为：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8;
dfs偏向一条路走到黑，只有无路可走的时候才会回头，回头一步之后继续查看还有没有每走过的路虽然dfs没有固定模板，我们这里还是用代码写一下dfs的基本流程
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
void dfs() {
// 如果满足终止条件，则回溯
if (terminated()) return ;
// 从当前节点继续向下搜索
dfs();
// 恢复现场，确保在同一节点看到的全局状态始终一致
back();
}
int main() {
cin >> n;
dfs();
return 0;
}bfs
广度优先搜索，顾名思义，该搜索方法会优先向更广的方向搜索。bfs是按照树的层级来遍历节点的，先遍历第一层的节点，再遍历第二层的节点，以此类推。
1
/ \
/ \
2 7
/ \ \
3 6 8
/ \
4 5
还是同样的一棵树，bfs的搜索顺序是：1 -> 2 -> 7 -> 3 -> 6 -> 8 -> 4 -> 5显然bfs是从根节点开始从距离最近的节点开始搜索，距离最近的所有节点都搜索完了之后才会搜索更远一层的节点，所以bfs先搜到的合法根节点一定是距离初始空间最近的节点。所以bfs通常用来解决最短路或者最优解问题。
因为bfs是按照一种类似于中序遍历的方式遍历搜索树，因此可以采用递归实现。对于bfs，因为优先搜索最近的节点，搜索完一个近距离的节点之后会产生距离更远的节点，但是这些远节点需要在近节点全部遍历完之后才能遍历，因此我们采用队列来存储搜索节点，搜索一个节点产生的子节点放入队列中，就可以保证先遍历完近节点再遍历远节点了，函数编写方式也从递归变成了循环。
不同于dfs，bfs是有一套固定模板的（也不算是模板，算是处理问题的流程吧）：
取出队头元素 -> 处理队头元素 -> 产生新的节点，插入队尾 ——————
^ |
| |
-------------------------------------------------bfs和dfs的比较
dfs是通过递归实现的，bfs是通过队列实现的，dfs会一直遍历到根节点才会停止，bfs会扩展每一层的节点。所以dfs的时间复杂度是O(h)，h为树的高度，bfs是按照层级遍历的，每层的每个节点都会产生数个新节点，时间复杂度为O(2n)。所以dfs的时间复杂的更好。值得一提的是，bfs更适合解决最优性问题或最短路问题，但是这是建立在所有边的权重都是1的前提下，如果边的权重不为1，则不能用bfs了，需要用专门的最短路问题来求解。
2.图的存储和遍历
存储图的方式主要分为两种：一种是邻接矩阵，另一种是邻接表。邻接矩阵就是一个二维数组，其中x,y下标的值为一表示图中从x点向y点有一条有向边，对于无向图，如果xy点之间有一条无向边，则可以将g[x][y]和g[y][x]都设置成1，如果边没有权重可以用0和1表示，如果边之间有权重，则数组的值就可以表示权重。邻接表则是使用链表存储图，每个节点都对应一个链表，如果该节点有指向另一个节点的有向边，则会将另一个节点加入该节点对应的链表中，链表中节点的顺序不重要，在新添加边时，一般会将边的终点头插进起点对应的链表中。
图的遍历方式也分为两种：dfs和bfs。dfs就是一直沿着一条线遍历，直到没有节点可走，然后回溯；bfs则是先遍历最近的节点，由近及远地遍历每个节点
图的dfs遍历（邻接表形式）
#include <iostream>
#include <ctring>
#include <algorithm>
using namespace std;
const int N = 10000;
// 存储形式和单链表类似，只是头节点从head单变量变成h[]数组了
int h[N], e[N], ne[N], idx;
bool st[N]; // 存储节点是否被遍历过
// 添加一条从a到b的边
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx ++;
}
// u为当前遍历到的节点编号
void dfs(int u) {
// 标记当前节点已经遍历过
st[u] = true;
// 从当前节点出发，寻找有哪些节点没有遍历过
for (int i = h[u]; i != -1; i = ne[i])
if (!st[e[i]])
dfs(e[i]);
}
int main() {
// 下一个节点为-1代表是空节点，也就是链表结尾
memset(h, -1, sizeof(h));
dfs(0);
return 0;
}树和图的遍历也是一种基本功，并没有很固定的模板，重要还是通过做题来增加熟练度，而且单独考察遍历图的题目也比较少，图的遍历一般是融合在解题过程中，即在遍历图的过程中完成对图的操作，如记录信息或修改等。
图的拓扑序列
一个图的拓扑序列定义为：对于图中的所有有向边(x, y)，x均出现在y前面，则该顶点序列称为拓扑序列。简单来说就是图中所有点都是有先后顺序的，不存在部分环的情况。不是所有图都有拓扑序列的，有环的图都没有拓扑序列，因为存在循环依赖的问题。可以证明：所有有向无环图都存在拓扑序列。拓扑序列可以用来解决一些具有先后次序的问题，例如课程的先修课问题。一个图的拓扑序列是不止一种的，通过拓扑排序可以得到一个图的拓扑序列。
拓扑排序的基本流程类似于bfs：首先记录所有点的入度和出度，挑选出所有入度为0的点加入搜索队列中（可以证明一个有向无环图必然存在至少一个入度为0的点），这些点因为没有边指向它们，所以可以作为拓扑序列的第一批节点，然后不断从队取出节点，遍历该节点所有的出边，删除这些边，同时将对应终点的入度减一，如果有点的入度变为0，则说明这些点的前置点已经处理完成，可以入队了。然后继续处理下一个节点，如此循环往复直到将队列中的点处理完，此时检查是否有没有处理过的点，如果有则说明该图不存在拓扑序列。如果所有点都处理过了，那么我们在前面处理的点的顺序可以构成该图的一个拓扑序列。
拓扑排序代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
// 存储图的邻接表
int h[N], e[N], ne[N], idx = 0;
int d[N], q[N]; // q是进行拓扑排序的队列，d存储每个点的入度
int hh = 0, tt = 0; // 队列指针
int n, m; // n为图的点数(点的编号从0开始），m为图的边数
// 添加一条从a指向b的有向边
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx ++;
}
bool top_sort() {
// 先将所有入度为0的点添加进队列中
for (int i = 0; i < n; i ++)
if (!d[i]) q[ ++ tt] = i;
while (tt > hh) {
int p = q[ ++ hh];
for (int i = h[p]; i != -1; i = ne[i]) {
int node = e[i];
d[node] --;
if (!d[node]) q[ ++ tt] = node;
}
}
return tt == n;
}
int main() {
cin >> n >> m;;
// 分别读入每条边
for (int i = 0; i < m; i ++) {
int a, b;
cin >> a >> b;
add(a, b);
d[b] ++; // 对应终点的入度 + 1
}
if (top_sort())
for (int i = 1; i <= n; i ++) cout << q[i] << " ";
else cout << "该图无拓扑序列";
return 0;
}拓扑排序例题：课程表。
3.最短路算法
有一类问题是要求我们求一个带权图中点与点之间的最短距离，这种问题称为最短路问题。
最短路问题可以分为如下几种：
单源最短路问题，即求某一对起点与终点之间的最短距离。单源最短路问题又可分为如下几种
图中无负权边：可以使用朴素Dijkstra算法或者堆优化Dijkstra算法解决。对于稠密图，使用朴素Dijkstra算法（时间复杂度O(n2)；对于稀疏图，使用堆优化的Dijkstra算法（时间复杂度O(m log n)；其中n为点的个数，m为边的数量。需要补充的是稠密图的定义是边数m和n2是相同数量级的图，稀疏图的定义是m和n是同一数量级的图。
图中有负权边：可以使用Bellman-Ford算法或SPFA算法解决
多源汇最短路问题（源就是起点，汇就是终点），即有多组询问，需要回答每组询问中的起点和终点之间的最短距离。
可以使用Floyd算法解决
需要指出的是：我们这里默认图都是有向图，因为无向图也是一种特殊的有向图，区别就是在为两个节点添加边的时候添加两条相反的有向边即可。
最短路算法的核心并不是在于会默写模板，而是在于建图，将问题转化为一个最短路问题的图，使用哪种信息作为图的边权重。这里只给出最简单的模板。
朴素Dijkstra算法
朴素Dijkstra算法是基于贪心的思想实现的。Dijkstra算法一般是用来求某一个点到其他所有点的最短距离的。其基本流程是：使用一个一维数组d存放起点到其他所有点的距离，使用另一个一维数组s存放当前已经确定最短距离的点，先将到起点（也就是本身）的距离设置成0，到其他点的距离设置成无穷大（一个很大的数）。接下来循环n 次，每次循环都将不在s中的距离起点最短的点加入s，然后用这个新加入的点更新其他所有点到起点的距离，每次循环会加入一个新的节点，循环n次就可以将全部点的最短距离都求出来。
朴素Dijkstra代码实现
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int g[N][N]; // 因为朴素Dijkstra算法一般用于稠密图，所以这里使用邻接矩阵存储图
int d[N];
bool st[N]; // 存储哪些点已经被遍历过了
int n, m; // n表示顶点的数量，m表示边的数量
// 这里默认求一号点到n号点的距离
int dijkstra() {
memset(d, 0x3f, sizeof d); // 初始化起点到所有点的距离为无穷大
d[1] = 0; // 先将起点1到自身的距离设置为1
for (int i = 0; i < n; i ++) {
int t = -1;
// 找出未加入集合s的距离起点最近的点
for (int j = 1; j <= n; j ++)
if (!st[j] && (t == -1 || d[j] < d[t])) t = j;
st[t] = true; // 将距离起点最近的点加入集合
// 用新加入的点更新其他点到起点的距离
for (int j = 1; j <= n; j ++)
d[j] = min(d[j], d[t] + g[t][j]);
}
// 如果d[n]没有被更新，说明从起点无法到达终点，返回特殊值
return d[n] == 0x3f3f3f3f ? -1 : d[n];
}
int main() {
cin >> n >> m;
memset(g, 0x3f, sizeof g); // 初始化所有点之间的距离为无穷大
// 图的输入，这里省略，但是要注意将所有的g[i][i]设置成0
for (int i = 1; i <= n; i ++)
g[i][i] = 0;
int t = dijkstra();
cout << t << endl;
return 0;
}时间复杂度分析：可以看到算法的核心是两重循环，每一重循环都固定循环n次，所以时间复杂度为O(n2)。
堆优化的Dijkstra算法
在朴素Dijkstra算法中，我们可以看到最耗时的操作是在每次循环中寻找距离起点最近的点加入集合中，而小根堆的特性就是根节点始终是最小的元素，我们可以在O(1)的时间内获取距离起点最近的点。因此堆优化Dijkstra算法的核心优化方向就是使用后堆来优化寻找距离起点最近的点的过程。我们在搜索的过程中需要不断更新每个顶点到达起点的距离，也就意味着要修改堆中的元素，但是在堆中修改元素是非常耗时的操作，这里采用的解决方法是冗余，即更新距离时直接插入新元组，新元组因为first更小会被先处理，所以当我们遍历时发现这个顶点已经被处理过了(st[i] == true)，则说明该元组是一个冗余，可以直接跳过。
堆优化Dijkstra算法代码实现
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
// 我们在堆中不仅要存储距离信息，还要存储这个距离是哪个点距离起点的，所以堆中存储的是pair元组
#define PII pair<int, int>
const int N = 1010;
// 因为堆优化Dijkstra算法一般用于稀疏图，所以用邻接表存储图，w数组存储每个边的权重
int h[N], e[N], ne[N], w[N], idx;
int d[N];
int n, m;
bool st[N]; // 存储是否被搜索过
priority_queue<PII, vector<PII>, greater<PII>> q; // 初始化小根堆
// 向图中添加一条从a指向b，权重为c的有向边
void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
int dijkstra() {
d[1] = 0;
// 插入一个元组，表示1号顶点距离起点的距离为0，因为优先队列需要按照距离排序，所以first存储的是距离，second存储顶点编号
q.push({0, 1});
while (q.size()) {
auto t = q.top();
q.pop();
int dis = t.first, node = t.second;
if (st[node]) continue; // 如果已经被搜索过，即当前元素是冗余，则直接跳过
// 有可能被更新的节点只能是跟该节点有边连接关系的节点，因此直接遍历h数组即可
for (int i = h[node]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] > dis + w[i]) {
d[j] = dis + w[i];
q.push({d[j], j}); // 更新之后需要将对应元素插入堆中
}
}
st[node] = true; // 标记已经搜索过
}
return d[n] == 0x3f3f3f3f ? -1 : d[n];
}
int main() {
cin >> n >> m;
memset(d, 0x3f, sizeof d);
memset(h, -1, sizeof h);
// 处理图的输入
for(int i = 0; i < m; i ++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = dijkstra();
cout << t << endl;
return 0;
}需要指出的是：无论是朴素dijkstra算法还是堆优化Dijkstra算法，都要求边权全部为正数，如果边权存在负值，那么两种Dijkstrra算法都不能使用了，就需要使用下面的Bellman-Ford算法或SPFA算法。
时间复杂度分析：对于外层while循环，因为最多会有m条边加入队列，因此外层循环最多为m次，对于内部循环，由于堆的删除和插入操作的时间复杂度为O(log n)， 同时因为是稀疏图，因此后面的for循环遍历的操作数量级会相对较低，可以忽略不计，总的时间复杂度为O(m log n)。
Bellman-Ford算法
Bellman-Ford算法可以处理有负权边的图。其核心流程是：存储所有边，每次遍历所有边，使用该边更新每个点到起点的距离，遍历n次结束，更新方式：d[b] = min(d[b], d[a] + w)。在选择数据结构时，因为Bellman-Ford算法只关心遍历所有边的结果，而不关心遍历顺序，因此存储边的方式肯定是越方便越好，这里选择使用结构体定义数组并存储边。
代码实现
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010; // 顶点数量的最大值
const int M = 1000000; // 边的数量的最大值
// 直接在定义结构体的时候定义数组
struct Edge {
int a; // 起点
int b; // 终点
int w; // 权重
} edges[M];
// n为顶点数量，m为边的数量
int d[N], backup[N];
int n, m, k;
int bellman_ford() {
d[1] = 0;
for (int i = 0; i < k; i ++) {
memcpy(backup, d, sizeof d);
for (int j = 0; j < m; j ++) {
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
d[b] = min(d[b], backup[a] + w);
}
}
return d[n] > 0x3f3f3f3f / 2 ? -1 : d[n];
}
int main() {
cin >> n >> m >> k;
memset(d, 0x3f, sizeof d);
// 输入所有边
for (int i = 0; i < m; i ++) {
int a, b, c;
cin >> a >> b >> c;
edges[i] = {a, b, c};
}
int t = bellman_ford();
cout << t << endl;
return 0;
}代码说明：该算法除了求最短路径以外，还有一个额外的功能：求k条边以内可以到达的最近距离，换句话说就是限制路径中包含的边不大于k，求出所有能求出来的路径最小值。Bellman-Ford算法的外层循环的实际意义是每次循环都会将已知的最短路径再扩展一步，所以如果题目要求在k条边以内求出最短距离，可以设置外层循环的最大次数，backup数组和24行的memcpy(backup, d, sizeof d);语句也是为了实现这个意义而存在的，可以看到我们更新d数组时使用的是d[b] = min(d[b], backup[a] + w);，backup数组存储的是上一轮的结果，只有这样才可以保证每次只扩展一条边。如果使用的是d[b] = min(d[b], d[a] + w);，则可能造成一种情况：在之前的循环中已经更新了 i 号节点，i 号节点在这次循环中扩展了一条边，而之后 j 节点通过i -> j这条边又扩展了一次，这样就导致一个串联的问题，即 j 节点在本轮循环中最短路径的边数直接 + 2，就不符合我们之前说的每次循环都只扩展一条边的实际意义了。关于返回值：因为可能存在负权边，因此即使有可能从起点根本无法到达终点，但是可能存在一条i -> n的边，边权为负，但是从起点根本无法到达i点，但是d[n]却会因为这条边变小，因此这里不去判断d[n] == 0x3f3f3f3f，而是判断d[n] 和 0x3f3f3f3f / 2的大小。
时间复杂度分析：假设图中没有负权环的话，最多n次循环就可以找到从起点到所有点的距离，时间复杂度为O(mn)。
SPFA算法
SPFA算法实际上是对Bellman-Ford算法的优化，其基本优化思路是：观察到整个算法的瓶颈在于d[b] = min(d[b], backup[a] + w);松弛操作，而只有backup[a]更新了才需要更新d[b]，否则就不需要更新，因此可以用一个队列来维护上一轮更新过的点，每次取出一个上一轮更新过的点，用这个点来更新到其他节点的距离。
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1010;
const int M = 1000000;
int h[N], e[N], w[N], ne[N], idx;
int d[N];
queue<int> q;
int m, n;
bool st[N]; // 存储当前节点是否已经在队列中
void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
int spfa() {
memset(d, 0x3f, sizeof d);
// 先初始化一号节点到自身的距离为0
d[1] = 0;
q.push(1);
st[1] = true;
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
// 遍历所有与该节点有关的边
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
// 如果可以更新，则更新距离，并且如果当前节点没有在队列中，需要添加进队列中
if (d[j] > d[t] + w[i]) {
d[j] = d[t] + w[i];
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return d[n] > 0x3f3f3f3f /2 ? -1 : d[n];
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
// 处理图的输入
for (int i = 0; i < m; i ++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = spfa();
cout << t << endl;
return 0;
}时间复杂度分析：一般是O(m)，但是最坏是O(mn)，最坏情况下会退化成Bellman-Ford算法。
Floyd算法
Floyd算法是求多源汇最短路问题最常用的算法，其基本思想是动态规划，实现代码非常简单.
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10100;
int n, m;
int d[N][N]; // 存储图，并且Floyd算法是直接操作原图的，所以只需要一个数组即可存储
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]);
}
int main() {
cin >> n >> m;
memset(d, 0x3f, sizeof d);
for (int i = 1; i <= n; i ++) d[i][i] = 0; // 节点到自身的距离为0
for (int i = 0 ;i < m; i ++) {
int a, b, c;
cin >> a >> b >> c;
d[a][b] = min(d[a][b], c); // 处理题目中可能存在重复边的问题
}
floyd();
cout << d[1][n] << endl; // 这里还是同样存在负权边的问题，需要判断d[1][n] > 0x3f3f3f3f / 2来判断是否可以到达
return 0;
}需要说明的是，Floyd算法可以用于有负权边的问题中，但是不能用于有负环的问题，因为有负环的图中可能不存在最短距离。
时间复杂度分析：三重循环，时间复杂度O(n3)。
补充知识：快速幂
这里补充一个简单的数学知识，或者说常用技巧，因为是一个小的知识点，不至于新起一章的篇幅讲解，所以在这里补充。
快速幂是用来快速求ak mod p 的值的，其中，1 <= a, k, p <= 109，在传统做法中我们需要对a连乘k次，时间复杂度为O(k)，而且还可能存在溢出的风险，快速幂便是为解决这个问题而衍生的，其时间复杂度为O(log k)，其基本思想是任何整数指数 b 都可以写成二进制形式，等价于拆成若干 2 的幂次之和。利用二进制求出k，我们先预处理出来a0 mod p，a2 mod p，a4 mod p，a8 mod p，···，alogk mod p的值，可以看到这些指数分别对应每一个二进制位，我们只需要求出k的每一位二进制位，如果为1就将a乘上对应位置的值即可。关于如何求出这些值，可以看到该一系列值的每一项都是前面一项的平方，因此可以不断平方前面的值来获取答案。
代码实现
#include <iostream>
#include <algotirhm>
using namespace std;
int a, k, p;
// 该函数的返回值就是a^k mod p 的值
int qmi() {
int res = 1;
while (k) {
if (k & 1) res = (long long) res * a % p;
k >>= 1;
a = (long long) a * a % p;
}
}
int main() {
cin >> a >> k >> p;
cout << qmi << endl;
return 0;
}