搜索与图论
2024年7月1日约 5209 字大约 17 分钟
搜索与图论
1. 树与图的存储
(1) 邻接矩阵：g [a] [b] 存储边 a -> b
(2) 动态邻接矩阵：
int n;
struct Edge
{
int id, w;
};
vector<Edge> h[N];
int dist[N];
void dfs(int u, int father, int distance)
{
dist[u] = distance;
for (auto node : h[u])
if (node.id != father)
dfs(node.id, u, distance + node.w);
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n - 1; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
h[a].push_back({b, c});
h[b].push_back({a, c});
}
dfs(1, -1, 0);
// 寻找两点之间的最大距离
int u = 1;
for (int i = 1; i <= n; i ++ )
if (dist[i] > dist[u])
u = i;
dfs(u, -1, 0);
for (int i = 1; i <= n; i ++ )
if (dist[i] > dist[u])
u = i;
int s = dist[u];
printf("%lld\n", s * 10 + s * (s + 1ll) / 2);
return 0;
}(3) 邻接表：
int n, m; //n代表点数，m代表边数
// 对于每个点k，开一个单链表，存储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);
//存边
for (int i = 0; i < n; i++){
int a, b;
cin >> a >> b;
add(a, b);
//无向图就再写一遍 add(b, a)
}2. 树与图的遍历
时间复杂度 O(n + m), n 表示点数， m 表示边数
深度优先遍历
int 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);
}
}宽度优先遍历
queue<int> q;
st[1] = true; // 表示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);
}
}
}3. 拓扑排序
时间复杂度 O(n+m), n 表示点数，m 表示边数
1、图的拓扑序列是针对于有向图而言的，无向图是没有拓扑序列的。有向无环图被称为拓扑图。
2、结论：一个有向无环图，一定至少存在一个入度为 0 的点。
bool topsort()
{
//采用数组模拟队列的写法，头尾指针
int hh = 0, tt = -1;
// d[i] 存储点i的入度，起点的入度为0
for (int i = 1; i <= n; i++)
if (!d[i]) //如果不是起点
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;
}
}
// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
return tt == n - 1;
}4. 最短路问题
4.1 单源最短路
求从一个点到其他所有点的最短距离。
分为两大类：
1、所有边权都是正数（n 个点，m 条边）
- 朴素版的Dijkstra算法，时间复杂度为 O(n2 + m) ，适合稠密图（边多，点少边比较多）
- 堆优化版的Dijkstra算法，时间复杂度为 O(mlogn)，适合稀疏图（点多，指边相对于点不多，m 和 n 是同一个级别的类型）
2、存在负权边
- Bellman-Ford 算法，时间复杂度为 O(nm)
- SPFA 算法，时间复杂度一般为 O(m)，最坏情况为 O(nm)，是Bellman-Ford算法的优化
4.1.1 朴素版 Dijkstra算法
稠密图用邻接矩阵，稀疏图用邻接表
1.逐个遍历，找到与起点最近的且未确定最短路径的点，访问加入集合并标记。
2.更新第一个点到起点的最短距离，直到第n个点。
__时间复杂度是 O(n2 + m)， n 表示点数，m 表示边数 __
#include <iostream>
#include <cstring>
#include <algortihm>
using namespace std;
const int N = 510;
int n, m; //点数和边数
int 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; // 在还未确定最短路的点中，寻找距离最小的点
//遍历n个点，找到一个未加入集合且距离最近的点
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];
}
int main()
{
cin >> n >> m;
//邻接矩阵初始化为无穷大
memset(g, 0x3f, sizeof(g));
while (m--){
int a, b, c;
cin >> a >> b >> c;
//存入a和b两点之间的距离（有向图）
g[a][b] = min(g[a][b], c);
//无向图
//g[a][b] = min(g[a][b], c);
//g[b][a] = min(a[a][b], c);
}
cout << dijkstra() << endl;
return 0;
}4.1.2 堆优化版的Dijkstra算法
稀疏图改用__邻接表__的形式存储，可以不需要考虑重边
时间复杂度是 O(mlogn)， n 表示点数，m 表示边数
#define PII pair<int, int>
int n; //点的数量
int h[N], w[N], e[N], ne[N], idx; //邻接表存储所有边
int dist[N]; //存储所有点到1号点的距离
bool st[N]; //存储每个点的最短距离是否已确定
void add(int a, int b, int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
// 求1号点到n号点的最短距离，如果不存在，则返回-1
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});
}
}
}
if (dist[n] == 0x3f3f3f3f)
return -1;
return dist[n];
}4.1.3 Bellman-ford算法（存在负权边）
1.可以用结构体存储点和边，包括负权边。
2.具体步骤：两重 for 循环，迭代 n-1 次，每次备份一下，每次循环遍历所有边，更新两点之间的最短距离，如点 a->b 的更新方式为（松弛操作）
for n 次
for 所有边 a, b, w (松弛操作)
dist[b] = min(dist[b], backup[a] + w);backup[ ] 数组是上一次迭代后 dist[ ] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[ ] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点。
3.循环 n-1 次之后，对于所有的点都 一定满足 dist[b] <= dist[a] + w，该式被称为三角不等式。
4.如果图中存在负权回路，那么最短路可能为负无穷。（不是一定）
5.是否能到达 n 号点的判断中需要进行 if(dist[n] > INF/2) 判断，而并非是 if(dist[n] == INF) 判断，原因是 INF 是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，``dist[n]大于某个与INF` 相同数量级的数即可。
6.bellman-ford算法擅长解决有边数限制的最短路问题。
时间复杂度 O(nm)， n 表示点数，m 表示边数
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
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;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}4.1.4 SPFA算法 （存在负权边）
1.用队列来存储
2.while queue 不为空，
- 取出作为 t ，t = q.front; q.pop();
- 更新 t 的所有出边，如：t -> b, 把b加入 queue
3.基本步骤
- 建立一个队列，初始时队列里只有起始点
- 再建立一个数组记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到它本身的路径赋为0）
- 再建立一个数组，标记点是否在队列中
- 队头不断出队，计算起始点经过队头到其他点的距离是否变短，如果变短且该点不在队列中，则把该点加入到队尾
- 重复执行直到队列为空
- 在保存最短路径的数组中，就得到了最短路径
4.SPFA求最短路
时间复杂度 平均情况下 O(m)， 最坏情况下 O(nm)， n 表示点数， m 表示边数
int n, m; // 总点数和总边数
int h[N], e[M], w[M], ne[M], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
int add(int a, int b, int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
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[t]; 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];
}4.1.5 SPFA算法判断图中是否存在负环
时间复杂度 O(nm)， n 表示点数， m 表示边数
int n; //总点数
int h[N], w[N], e[N], ne[N], idx; //邻接表存储所有边
int dist[N]; //dist[x]存储1号点到x的最短距离，
int cnt[N]; //cnt[x]存储1到x的最短路中经过的点数
bool st[N]; //存储每个点是否在队列中
// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
// 不需要初始化dist数组
// 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
queue<int> q;
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;
// 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
if (cnt[j] >= n) return true;
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}4.2 多源汇最短路
4.2.1 Floyd算法
1.使用邻接矩阵存图
2.三重循环，时间复杂度O(n^3)
初始化：
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;
//算法结束后，d[a][b]表示a到b的距离
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]);5. 最小生成树问题
最小生成树就是将 n 个顶点， n - 1 条边，通过一个连接起来，且使权值最小的一种结构。
换句话来说，就是给定一个无向图，在图中选择若干条边把图中的所有节点连接起来，要求边长之和最小。在图论中，叫做求最小生成树。
5.1 朴素Prim算法
可理解为 “加点法”， 每次迭代找到不在连通块中的距离最近的点，加入到连通块中，将连通块逐渐扩大，最后将整个图连通起来，并且边长之和最小。
1、先把所有距离初始化为正无穷
dist[i] = +INF;2、n次迭代，找到不在集合当中的最小的点，这个集合指当前已经在连通块中的所有点，找到该点赋给 t ，用 t 更新其他点到集合的距离，再把 t 加到集合当中去
先累加，再更新
for (int i = 0; i < n; i++)
t <- 距离最近的点;
t = ture;更新t时间复杂度为 O(n2 + m)， n 表示点数， m 表示边数
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int n, m; // n表示点数，m表示边数
int g[N][N]; // 邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0; //最小生成树所有边的长度之和
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;
//一定要先累加，再进行更新生成树
if (i && dist[t] == INF)
return INF;
if (i) //(不是起点)把找到的符合条件的点的长度加上
res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j++)
dist[j] = min(dist[j], g[t][j]);
}
return res;
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= m; i++){
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = prim();
if (t == INF) puts("impossible");
else printf("%d\n", t);
}5.2 Kruskal 算法
可理解为 “加边法”，最初最小生成树的边数为 0，每次迭代选择一条不在集合内的权值最短的边，加入到集合中，组成最小生成树。
1、使用快排将所有边按权值从小到大排序。时间复杂度为 O(log n).
2、从小到大依次枚举每组边 a 、b，权重 c ，如果 a、b不连通，就将这条边加入集合中，直到具有 n 个顶点的连通块筛选出来 n-1 条边为止。时间复杂度为 O(n) .
3、判断 a、b是否连通的方法为：使用并查集。
- 初始化各个顶点在不同的集合中，父节点为它自己。
- 按快排的从小到大的顺序遍历每条边，判断这条边的两个顶点是否有相同的父节点，如果有那就使在同一个集合中。
- 如果该条边上的两个顶点在一个集合中，说明两个顶点已经连通，这条边不要。如果不在一个集合中，则加入这条边到集合中，连通这两个顶点。
时间复杂度是 O(mlogm)， n 表示点数， m 表示边数
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m; // n是点数，m是边数
int p[N]; // 并查集的父节点数组
int rank[N]; // 树的高度
//结构体存储 两点及其权值
struct Edge
{
int a, b, w;
//重载小于号，因为再给边排序的时候是按照边的权重进行排序的，这样当两个边进行比较的时候就会使用他们的权重进行比较了
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];
void init(int n)
{
for (int i = 1; i <= n; i++){
p[i] = i;
rank[i] = 0;
}
}
int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void union(int x, int y)
{
int px = find(x), py = find(y);
if (px == py) return;
if (rank[px] < rank[py]){
p[px] = py;
}
else {
p[py] = px;
if (rank[px] == rank[py])
rank[px]++;
}
}
int kruskal()
{
sort(edges, edges + m);
init(n);
int res = 0; //存的是最小生成树的所有边的权值
int cnt = 0; //存的是当前加入的边数
for (int i = 0; i < m; i++)
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
pa = find(a), pb = find(b);
if (pa != pb) // 如果两个连通块不连通，则将这两个连通块合并
{
union(a, b);
res += w;
cnt++;
}
}
//只有当 cnt == n - 1 时才能表示已经将所有点加入到集合中，可以生成最小生成树
if (cnt < n - 1)
return INF;
return res;
}6. 染色法判别二分图
二分图： 将所有点分成__两个集合__，使得__所有边__只出现在集合之间，就是 二分图
性质： 一定不含有奇数环，可能包含长度为偶数的环，不一定是__连通图__。
DFS思路：
- 染色可以使用
1和2区分__不同颜色__，用0表示 未染色 - 遍历所有点，每次将__未染色的点__进行
dfs，默认染成1或2 - 由于某个点染色成功并不代表整个图就是二分图，因此只有某个点染色失败才能立刻
break/return，__染色失败__相当于存在两个相邻的点染成了相同的颜色
时间复杂度 O(n + m)， n 表示点数，m 表示边数
int n, m; //n表示点数，m表示边数
int h[N], e[M], ne[M], idx; //邻接表存储图
int color[N]; //表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色
//参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (color[j] == -1)
{
if (!dfs(j, !c))
return false;
}
else if (color[j] == c)
return false;
}
return true;
}
bool check()
{
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i ++ )
if (color[i] == -1)
if (!dfs(i, 0))
{
flag = false;
break;
}
return flag;
}7. 匈牙利算法
相关概念：
匹配：在图论中，一个 [匹配] 是一个边的集合，其中任意两条边都不依附于同一个顶点。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路。
增广路：从一个未匹配路出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路。
算法描述：
如果你想找的妹子已经有了男朋友，
你就去问问她男朋友，
你有没有备胎，
把这个让给我好吧
多么真实而实用的算法
tips：因为你要去问的都是男孩子，所以存边的时候，都是由男孩子指向女孩子
时间复杂度是 O(nm)， n 表示点数，m 表示边数
int n1, n2; //n1表示第一个集合中的点数，n2表示第二个集合中的点数
// 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int h[N], e[M], ne[M], idx;
int match[N]; //存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; //表示第二个集合中的每个点是否已经被遍历过
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);
if (find(i))
res++;
}