算法笔记-图论基础
定义图中，n为点数，m为边数
m= $O(n^2)$，则认为是稠密图
m = $O(n)$，则认为是稀疏图
树与图的存储
- 邻接表，适用于稀疏图
1
2
3
4
5
6const int N = 1e6+5;
int h[N], e[N], ne[N], idx = 0;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
} - 邻接矩阵，适用于稠密图
1
2const int N = 1e6+5;
int g[N][N];
深度优先搜索 DFS
- 用栈或函数递归来实现
朴素DFS遍历图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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const int N = 1e6+5;
int h[N], e[N], ne[N], idx = 0;
int st[N], n, m;
int stk[N], top = 0;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 递归版
void dfs(int u) {
if (st[u]) return;
printf("%d -> ", u);
st[u] = 1;
int node = h[u];
while (node != -1) {
dfs(e[node]);
node = ne[node];
}
}
// 迭代版
void dfs(int u) {
// init stack
stk[top] = 0;
while (top >= 0) {
// pop from stack
int node = stk[top--];
st[node] = 1;
printf("%d -> ", node);
for (int i = h[node]; i != -1; i = ne[i]) {
if (st[e[i]]) continue;
stk[++top] = e[i];
}
}
}
int main() {
// init
memset(h, -1, sizeof(h));
memset(st, 0, sizeof(st));
// build graph
scanf("%d%d", &n, &m);
while(m--) {
int a, b;
scanf("%d%d", &a, &b);
add(a,b);
add(b, a);
}
dfs(0);
return 0;
}
例题：回溯&剪枝， Leetcode 46. 全排列
1 | class Solution { |
宽度优先搜索 BFS
- 用队列实现
走迷宫（最短路）
1 |
|
| 数据结构 | 空间 | 特点 | |
|---|---|---|---|
| DFS | 栈 | O(h) | 不具有最短性 |
| BFS | 队列 | $O(2^h)$ | 最短路 |
拓扑排序
有向无环图的拓扑排序通过实时计算每个点的出度入度来实现
- 出度：该节点直接连接到其他点的路径数
- 入度：其他点直接到该点的路径数
有向无环图必然存在入度为0的点
思路：
- 找出所有入度为0的点，加入队列
- 每从队列取出一个点a，便打印该点，标记为已经遍历，并遍历它的所有出边(a -> b)，将b的入度减一；若b的入度变为0，则将b节点加入队列
- 重复步骤2，至队列为空例题：MarsCode, 94.数据表是否能顺利产出
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
35
36
37
38
39
40
41
42
43
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], d[N],idx = 0;
void add(int u, int v) {
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
int main() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof(h));
memset(d, 0, sizeof(d));
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
d[b]++;
}
// find in-degree
queue<int> q;
for (int i = 1; i <= n; i++) if (d[i] == 0) q.push(i);
// topological sort
while (!q.empty()) {
int u = q.front();
q.pop();
printf("%d ", u);
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
d[j]--;
if (d[j] == 0) q.push(j);
}
}
return 0;
}
1 |
|
最短路问题
单源最短路
边权为正
- 朴素Dijkstra算法（O(n^2)），适用于稠密图
- 堆优化版Dijkstra算法(O(mlogn))，适用于稀疏图
朴素Dijkstra
步骤：
- 找到当前距离源点最近的点N
- 标记访问
- 更新以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
30const int N = 1000;
int n, m;
int g[N][N];
int dis[N];
int vis[N];
int dijkstra() {
// init
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
for (int i = 0; i < n; i++) {
// find shortest path
int t = -1;
for (int j = 1; j <= n; j++)
if (!vis[j] && (t == -1 || dis[j] < dis[t])) t = j;
// mark visited
vis[t] = 1;
// update distance
for (int k = 1; k <= n; k++)
if (g[t][k] != 0x3f3f3f3f)
dis[k] = min(dis[k], dis[t] + g[t][k]);
}
return dis[n];
}
堆优化Dijkstra
1 | using namespace std; |
复杂度解释：
- 优先队列操作：图中每个边最多被添加或删除一次，故为$O(mlogn)$
- 遍历边操作：在遍历每条边时，可能会更新邻居节点的距离，并将其插入优先队列，总时间复杂度是 $O(mlogn)$
故总复杂度应该是$O(mlogn)$
边权可为负
边权可为负的图中，若存在负权回路，则与源点间存在经过负环的路径的节点不存在最短路
- Bellman-Ford(O(nm))
- SPFA(O(m), 最坏O(nm))
Bellman-Ford
- 可以找出负环（鸽巢原理）
- 结果满足三角不等式$dist[b] \le dist[a] + w$
- 图中允许存在负环
- 可以解决限制经过边数的最短路问题
算法思路：循环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
25const int N = 1e5 + 5;
// 存边即可
struct Edge {
int a, b, w;
} E[N];
int dis[N];
int backup[N];
int n, m, k;
// 返回到第n点的最多经过k段的最短距离
int bellman_ford() {
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
for (int i = 0; i < k; i++) {
memcpy(backup, dis, sizeof dis);
for (int j = 0; j < m; j++) {
int a = E[j].a, b = E[j].b, w = E[j].w;
if (backup[a] == 0x3f3f3f3f) continue;
dis[b] = min(backup[b], backup[a] + w);
}
}
return dis[n];
}
SPFA
- 可以判断负环是否存在 (鸽巢原理)
- 效率比bellman_ford高
思路：初始化队列，队列初始只有一个源点；之后不断迭代，每从队列头取出一个节点，就跟新它的所有出边，并将邻居节点加入队列，直至队列为空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
31const int N = 1e6+5;
int h[N], e[N], ne[N], w[N], idx = 0;
int dis[N], cnt[N], vis[N];
queue<int> q;
int n, m;
int spfa() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[1] = 0;
q.push(1);
vis[1] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = false;
for (int i = h[u]; ~i; i = ne[i]) {
if (dis[e[i]] > dis[u] + w[i]) {
// 判断是否存在负环
if ((cnt[e[i]] = cnt[u] + 1) >= n) {
return 0x3f3f3f3f;
}
dis[e[i]] = dis[u] + w[i];
if (!vis[e[i]]) {
vis[e[i]] = true;
q.push(e[i]);
}
}
}
}
return dis[n];
}
多源最短路 Floyd
- Floyd算法($O(n^3)$)
- 不能处理具有负环的图
思路：依次选择一个点为中转点，计算每两个点之间的最短路
归纳证明：$d[k, i, j] = min(d[k-1, i, j], d[k-1, i, k] + d[k-1, k, j])$，其中$d[k-1,i,j]$表示从顶点i到顶点j，且中间顶点仅取自${1,2,…,m-1}$的最短路长度1
2
3
4
5
6
7
8
9
10void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (d[i][k] == INF || d[k][j] == INF) continue;
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
最小生成树
最小生成树问题一般针对无向图
最小生成树算法有两个：
- Prim算法
- Kruskal算法
两者都是基于贪心的思想
Prim
与Dijkstra算法非常想，也有朴素版（$O(n^2)$）和堆优化版（$O(mlogn)$），分别适用于稠密图和稀疏图。这里仅介绍朴素版。
思路：
- 初始化生成树集合，所有点到该集合的距离设为无穷
- 找到集合外随便一点，加入集合，并以该点更新其他店到集合的距离
- 进行N-1次循环，每次循环找到集合最短的出边，并将对应的点加入集合，且以新加入的点更新集合外其他点到集合的距离
1 | const int N = 105, INF = 0x3f3f3f3f; |
Kruskal
复杂度为$O(mlogm)$，适用于稀疏图，与Prim堆优化版算法更推荐Kruskal算法。
同$O(mlogn)$, 因为$m \le n^2$
思路：
- 初始化生成树集合，为空
- 将所有边按权重从小到大排序 $O(mlogm)$
- 依次枚举每条边a-b：$O(m)$
- if a-b不连通（指在集合中，可用并查集进行判断），则将边ab加入集合
1 |
|
二分图
定义：一个图的所有顶点，可以把所有顶点分为两个顶点集合，每个集合中两两不直接相连。
一个图是二分图，当且仅当图中不含奇数环
二分图相关的算法有两个：
- 染色法
- 匈牙利算法
染色法
该算法可以判断一个图是否为二分图，复杂度为$O(n+m)$
思路：DFS遍历每个点，是每相邻两个点分到不同集合
1 |
|
匈牙利算法
该算法可以解决二分图最大匹配问题，复杂度为$O(mn)$，实际运行时间远小于$O(mn)$
匹配是指一组边的集合，其中任意两条边都没有共同的顶点。
思路：
- 将二分图的点分为两个点集AB，保存A到B的路径信息
- 遍历A的每个点a，遍历连接a的点b
- 如果b还没被匹配，使a匹配b，并记录match[b] = a
- 如果b被匹配，则尝试使match[b]匹配其他节点（），如果成功则记录match[b] = a，否则a无法找到匹配
1 |
|
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 多巴胺の小窝！
微信
支付宝
评论