第三章 图论
图的存储
邻接表的存储
- 适用于稀疏图的存储
// N为点的数量，M为边的数量，
const int N = 1e5+10, M = 2 * N;
int e[M], h[N], ne[M], w[M];
// 遍历邻接表
for (int i = h[a]; i != -1; i = ne[i]) {
// a->j存在一条边
int j = e[i]; //j为顶点
int w1 = w[i]; //w1为a->j的边权
}
邻接矩阵的存储
- 适合于稠密图的存储
// N为点的数量
int g[N][N];
// 遍历邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//g[i][j]
}
}
单源最短路算法
- Dijkstra只能用于求非负权图
- bellman-ford可以用于求解带负权图
- spfa不能求解带负权环路的最短路径
dijkstra算法(朴素版)
时间复杂度：O(n2+m)
算法过程
求点a的单源最短路径
1. 初始化dis[i] = inf, dis[a] = 0；
2. 循环n次，其中n为顶点的数量；
3. 循环的步骤如下：
选出从未访问过的结点，距离最短的点；
用该点更新到其他未被访问的结点的距离（距离更短时才更新）
4. dis[i] = inf说明无法到达该结点，否则，到结点i的距离即为dis[i]；
模板
邻接矩阵存储
int dijkstra() {
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
for (int i = 1; i <= n; i++) {
int k = -1;
for (int j = 1; j <= n; j++) {
if (!t[j] && (k == -1 || dis[j] < dis[k])) {
k = j;
}
}
t[k] = true;
for (int i = 1; i <= n; i++) {
if (dis[i] > dis[k] + graph[k][i]) {
dis[i] = dis[k] + graph[k][i];
}
}
}
if (dis[n] == 0x3f3f3f3f) {
return -1;
} else {
return dis[n];
}
}
注意点
- 只能用于边权为正的有向图和无向图
- 可以处理带自环和重边，在读入的时候（邻接表无需特别处理，邻接矩阵取最短的那条）
dijkstra算法（堆优化）
时间复杂度：O(mlog(n))
算法过程
- 基本的算法流程是和朴素版一样的，但是对于朴素版而言，在选出从未访问过的结点时，需要
O(n)的时间复杂度，因此，对这部分进行优化，利用小根堆将时间复杂度降至O(logn) - 优化过程，距离更新时，每次将被更新过的距离入队，可能某一点的距离入队很多次，但是只会出队一次，在出队时，考虑该结点是否被访问，如果被访问过，则是不进行更新距离的
模板
邻接表存储
void dijkstra() {
memset(dis, 0x3f, sizeof dis);
priority_queue<PII, vector `<PII>` ,greater `<PII>`> q;
dis[1] = 0;
q.push({0, 1});
while (q.size()) {
auto top = q.top();
q.pop();
int ver = top.second, distance = top.first;
if (vis[ver]) {
continue;
}
vis[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (dis[j] > dis[ver] + w[i]) {
dis[j] = dis[ver] + w[i];
q.push({dis[j], j});
}
}
}
if (dis[n] == 0x3f3f3f3f) {
cout << "-1";
} else {
cout << dis[n];
}
}
bellman-ford算法
时间复杂度：O(nm)
算法过程
- 执行以下n次；
- 对每条边都进行松弛，即执行
dis[b] = min(dis[b], dis[a] + w);
注意点
- 如果题目要求经过k条边的最短路径，则需要有一个backup数组，以免发生串联；
- 如果题目没有要求经过k条边的最短路径，只要求单源最短路径，发生串联是无所谓的；
- 如果要求
a的单源最短路径，最开始的更新为：dis[a] = 0； - 如果不存在负权边，最短距离不存在为
dis[a] = 0x3f3f3f，存在负权边，最短距离不存在为dis[a] > 0x3f3f3f3f / 2
模板
// 初始时，dis[a] = 0，则求的为a到x的单源最短路径；
void bellman_ford() {
memset(dis, 0x3f, sizeof dis);
dis[2] = 0;
for (int i = 0; i < k; i++) {
memcpy(backup, dis, sizeof backup);
for (int j = 0; j < m; j++) {
int a = edge[j].a, b = edge[j].b, w = edge[j].w;
dis[b] = min(dis[b], backup[a] + w);
}
}
if (dis[n] > 0x3f3f3f3f / 2) {
cout << "impossible";
} else {
cout << dis[n];
}
}
SPFA算法 (优化版的Bellman-ford算法)
时间复杂度： 最好：O(m), 最差：O(nm)
SPFA算法是对Bellman-ford算法的一个改进。在进行更新的时候，SPFA算法是对所有的边都要进行更新，但实际上只有dis被更新顶点才有资格去更新别人，根据这一点将可以更新别人的点加入队列中，同时记得需要进行记录该点是否在队列中，以免重复加入。
模板
该模板和优化的Dijkstra算法是否相似
void spfa() {
memset(dis, 0x3f, sizeof dis);
queue `<int>` q;
q.push(1);
dis[1] = 0;
vis[1] = true;
while (q.size()) {
auto t = q.front();
q.pop();
vis[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dis[j] > dis[t] + w[i]) {
dis[j] = dis[t] + w[i];
if (!vis[j]) {
q.push(j);
vis[j] = true;
}
}
}
}
if (dis[n] > 0x3f3f3f3f / 2) {
cout << "impossible";
} else {
cout << dis[n];
}
}
注意点
- 该算法不能求存在负权回路的图
- 该算法也常被用来求解非负权边的图，如果非负权边的被卡，换成其他算法进行求解，例:优化版的Dijkstra算法
SPFA算法判负环
时间复杂度: O(nm)
如果图中所具有n个顶点，一条最短路径经过n−1条，那么，根据抽屉原理，必定存在一个环。又因为这能使得路径变短，这个环必然是负环。
模板
每进行更新一次，最短路径所经过的边数+1；
bool spfa() {
queue `<int>` q;
for (int i = 1; i <= n; i++) {
q.push(i);
vis[i] = true;
}
while (q.size()) {
int t = q.front();
q.pop();
vis[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dis[j] > dis[t] + w[i]) {
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) {
return true;
}
dis[j] = dis[t] + w[i];
if (!vis[j]) {
q.push(j);
}
}
}
}
return false;
}
注意点
- 在SPFA算法的基础上，只要增加一个记录最短路径经过的边数的数组。如果dis[x]>=n，则说明从
x出发的最短路径上必定存在负环； - 若存在负环路径必定比0小，因此，可不必初始化
dis数组 - 负环不一定在从1出发的最短路径上，因此，在最开始的时候必须把所有的结点都入队
最小生成树
prim
适用于稠密图
时间复杂度为：O(n2+m)
- 以下过程循环n次；
- 找出一个未加入集合但距离集合中的点最近的点
- 如果不是第一个点同时距离为无穷，则不存在最小生成数；（在第一个点的时候，距离为无穷的，因为第一次循环时，所有距离都是无穷，应该需要在不是第一次循环的时候判断距离为无穷说明不存在最小生成树）；
- 用该点去更新其他点到集合的距离；
- 将该点加入集合中同时记算生成树的权重（如果不是第一次就要进行累加）
设置 dis[1] = 0，可以避免判断 i是否为第一次的情况，同时累加时，可不用进行判断，因为 dis[1] = 1不会影响答案。
模板
void prim() {
int res = 0;
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
if (!vis[j] && (t == -1 || dis[j] < dis[t])) {
t = j;
}
}
if (dis[t] == 0x3f3f3f3f) {
cout << "impossible";
return;
}
vis[t] = true;
res += dis[t];
for (int j = 1; j <= n; j++) {
dis[j] = min(dis[j], q[t][j]);
}
}
cout << res;
}
注意点
- 算法模板和朴素版的Dijkstra算法十分类似，注意区分
- 与Dijkstra算法不同的地方在于：Dijkstra算法在更新的时候是更新到起点的距离，而Prim算法更新的是到已加入集合的距离
kruskal
适用于稀疏图
时间复杂度为： O(mlog(m))
- 将边权从小到大排序；
- 当该边的端点不都在集合中，将该边加入，否则，舍弃该边；
- 重复1-2直至加入
n - 1条边
模板
int find(int x) {
if (f[x] != x) {
f[x] = find(f[x]);
}
return f[x];
}
for (int i = 0; i < m; i++) {
int a = find(Edge[i].a), b = find(Edge[i].b);
if (a != b) {
cnt++;
f[a] = b;
res = res + Edge[i].w;
if (cnt == n - 1) {
break;
}
}
}
染色法判断二部图（二分图、偶图）
如果图是二部图当且仅当它可以被二染色。
模板
bool dfs(int x, int c) {
color[x] = c;
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
if (!color[j]) {
if (!dfs(j, 3 - c)) {
return false;
}
} else if (color[j] == c) {
return false;
}
}
return true;
}
匈牙利算法求二部图的最大匹配
每次进行回溯试探能否对于当前匹配对象的对象能否找到另一个对象，使得当前的点能够于匹配该对象。
模板
bool find(int a) {
for (int i = h[a]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
st[j] = true;
if (match[j] == 0 || find(match[j])) {
match[j] = a;
return true;
}
}
}
return false;
}
注意点
- 只需要存储二部图的左半部结点到右半部结点的边，同理，也可以只存储右半部到左半部的边
DFS 深度优先搜索
自己整理的模板
// 8个方向的dfs
int dx[4] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[4] = {0, 1, 0, -1, 1, -1, -1, 1};
// 4个方向的dfs
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void dfs(int x, int y) {
for (int i = 0; i < 4; i++) {
int x1 = dx[i] + x, y1 = dy[i] + y;
if (x1 < 0 || y1 < 0 || x1 >= g.size() || y1 >= g[i].size() || vis[x1][y1]) {
continue;
} // 该条件可以在附带剪枝条件
vis[x1][y1] = true;
dfs(x1, y1);
}
}
BFS 广度优先搜索
可以用于解决边权值相等（不止是边权为1是才可以用）的最短路径问题。
自己整理的模板
// 遍历网格(m x n)的BFS
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
queue<具体结构> q;
while (q.size()) {
auto t = q.front();
q.pop();
int x = q.first, y = q.second; //看具体结构
for (int i = 0; i < 4; i++) {
int x1 = dx[i] + x, y1 = dy[i] + y;
if (x1 < 0 || y1 < 0 || x1 >= n || y1 >= m || vis[x1][y1]) {
continue;
}
vis[x1][y1] = true;
//具体逻辑部分
}
}
双端BFS
与Dijkstra算法类似
用以解决只有边权只有0和1的最短路径问题
满足两段性和单调性，前一段和后一段的差值为1；
主要思路：
- 与BFS类似的，将权值为0放在队头， 将权值为1的放在队尾；
- 某个点只能被访问一次，可以多次入队；
模板
// 遍历网格(m x n)的BFS
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
dequeue<具体结构> q;
while (q.size()) {
auto t = q.front();
q.pop_front();
int x = q.first, y = q.second; //看具体结构
//只能最多只被访问1次
if (vis[x][y]) {
continue;
}
for (int i = 0; i < 4; i++) {
int x1 = dx[i] + x, y1 = dy[i] + y;
if (x1 < 0 || y1 < 0 || x1 >= n || y1 >= m || vis[x1][y1]) {
continue;
}
if (g[x][y] == 0) {
// 权值为0在队头
q.push_front();
q.
} else {
//权值为1放在队尾
q.push_back();//
}
//具体逻辑部分
}
}
多源BFS
第一次入队时，并不是只有一个点，而是将所有满足条件的点入队，初始时，队列并不是只有一个点，而是具有多个点
最小步数
将一个点（图）当做一个状态，而不是将图上的点当作一个状态，通常用hash表来存储该状态是否被访问过，其他与BFS类似
拓扑排序
拓扑排序：只有从前指向后的边，没有从后指向前的边
算法过程
（n为顶点的数量）
- 将入度为0的点入队
- 将队列中的点出队，同时将该点所连接的点的度-1，若删除后，所连接的点的度为0，则将该点入队
- 判断是否队列中曾经入队过为n次，如果是，则队列中依次出队的顺序即为拓扑排序，否则，不存在拓扑排序
注意点
- 有向无环图一定存在拓扑排序，有向有环图一定不存在拓扑排序
- 采用数组模拟的队列从下标为
0 - n-1即为拓扑排序；如果用stl的库函数，则需要额外开辟一个数组用来记录拓扑排序，如果该数组的大小为n，则说明具有拓扑排序，反之，不具有拓扑排序。
模板
void bfs() {
hh = 0, tt = -1;
for (int i = 1; i <= n; i++) {
if (d[i] == 0) {
q[++tt] = i;
}
}
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (--d[j] == 0) {
q[++tt] = j;
}
}
}
if (tt == n - 1) {
for (int i = 0; i < n; i++) {
cout << q[i] << " ";
}
} else {
cout << "-1";
}
}
