目录

本文目录

  • 图论简介
  • 邻接矩阵
  • 边集数组
  • 邻接表
  • 链式邻接表
  • 链式前向星
  • 小结

图论简介

图论 (Graph theory) 是数学的一个分支,图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关系。本文将着重讲解建图存边的几种方法,主要学习如何定义、如何建边、如何访问,并且分析时间、空间复杂度以及应用场景。

邻接矩阵

定义一个二维数组 g[u][v]g[u][v] 存储点 uu 到点 vv 的边权。
初始化建边时,只需要暴力枚举所有的边即可
假设给定所有点之间对应的边权矩阵,只需要暴力枚举所有的边即可建边。

1
2
3
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) cin >> g[i][j];
}

如果给定mm条边,也很简单,枚举所有边

1
2
3
4
5
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u][v] = w;
}

当我们需要访问时(这里假设用dfs访问整张图),代码如下

1
2
3
4
5
6
7
8
9
10
bool vis[MAXN];

void dfs(int u) {
vis[u] = true;
for (int v = 1; v <= n; v++) {
if (!g[u][v]) continue;
cout << u << ' ' << v << ' ' << g[u][v] << '\n';
if (!vis[v]) dfs(v);
}
}

时间复杂度:O(n2)O(n^2)

空间复杂度:O(n2)O(n^2)

适用于点数不多的稠密图,因为初始化的复杂度就已经很大了。

边集数组

我们使用一个结构体数组来存储起点u、终点v和边权w起点u、终点v和边权w,这样我们就不用枚举任意两个点的点关系,大大降低了复杂度

具体操作如下

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
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

struct Edge { int u, v, w; };
vector<Edge> edges;
vector<bool> vis;

void dfs(int u) {
vis[u] = true;
for (auto [a, v, w] : edges) {
if (a != u) continue;
cout << u << ' ' << v << ' ' << w << '\n';
if (!vis[v]) dfs(v);
}
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vis.assign(n + 1, false);
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({u, v, w});
}
dfs(1);
return 0;
}

时间复杂度:O(nm)O(nm)

空间复杂度:O(m)O(m)

应用:常用于Kruskal算法中,按边权排序存边

邻接表

使用vector维护一个出边数组G[u][i]G[u][i],存储点uu的所有出边以及边权

本博客后续大多数图论内容也将以此为基础进行展开,大多数情况下采取此种方法进行建边

实现代码:

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
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

struct Edge { int v, w; };
vector<vector<Edge>> g;
vector<bool> vis;

void dfs(int u) {
vis[u] = true;
for (auto [v, w] : g[u]) {
cout << u << ' ' << v << ' ' << w << '\n';
if (!vis[v]) dfs(v);
}
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
g.resize(n + 1);
vis.assign(n + 1, false);
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1);
return 0;
}

时间复杂度:O(n+m)O(n+m)

空间复杂度:O(n+m)O(n+m)

普通的 vector 邻接表没有直接记录反向边编号。网络流中通常把正向边与反向边成对存储,再在邻接表里保存边的编号,这就是下面的链式邻接表写法。

链式邻接表

使用两个数组,一个边集数组e[j]e[j]存储第jj条边的起点终点和边权

然后使用一个表头数组G[u][i]G[u][i]存储点uu的所有出边

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
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

struct Edge { int u, v, w; };
vector<Edge> edges;
vector<vector<int>> g;
vector<bool> vis;

void add(int u, int v, int w) {
edges.push_back({u, v, w});
g[u].push_back(static_cast<int>(edges.size()) - 1);
}

void dfs(int u) {
vis[u] = true;
for (int id : g[u]) {
auto [a, v, w] = edges[id];
cout << a << ' ' << v << ' ' << w << '\n';
if (!vis[v]) dfs(v);
}
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
g.resize(n + 1);
vis.assign(n + 1, false);
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dfs(1);
return 0;
}

时间复杂度:O(n+m)O(n+m)

空间复杂度:O(n+m)O(n+m)

应用:可以应用到各种图,并且可以处理反向边

链式前向星

我们使用两个数组,一个数组head[i]head[i]就是以ii为起点的第一条边的存储位置

edgeedge数组是一个边集,存边的信息

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
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

const int MAXN = 100005, MAXM = 200005;
struct Edge { int to, w, nxt; } edges[MAXM];
int head[MAXN], cnt;
bool vis[MAXN];

void add(int u, int v, int w) {
edges[cnt] = {v, w, head[u]};
head[u] = cnt++;
}

void dfs(int u) {
vis[u] = true;
for (int i = head[u]; i != -1; i = edges[i].nxt) {
auto [v, w, nxt] = edges[i];
cout << u << ' ' << v << ' ' << w << '\n';
if (!vis[v]) dfs(v);
}
}

int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
fill(head, head + n + 1, -1);
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
dfs(1);
return 0;
}

时间复杂度:O(n+m)O(n+m)

空间复杂度:O(n+m)O(n+m)

应用:可以用于所有图,可以处理反向边

总结与常见问题

常见问题

  • 邻接矩阵中的 0 一定表示没有边吗? 不一定。如果题目允许边权为 00,就要使用额外的布尔数组或特殊值表示“无边”。
  • 无向边为什么要加入两次? 邻接表存的是出边。无向边 u−vu-v 等价于 u→vu\to v 与 v→uv\to u 两条有向边。
  • DFS 为什么只记录 fa 有时不够? fa 只适合树或确定没有其他环的场景;一般图必须使用 vis 数组防止沿环重复访问。
  • 网络流为什么常保存边的编号? 正向边与反向边通常成对加入,保存编号后可以用 id ^ 1 快速找到对应反向边并修改剩余容量。

复杂度分析

  • 邻接矩阵:建图和空间复杂度均为 O(n2)O(n^2),枚举一个点的所有可能邻点为 O(n)O(n)。
  • 边集数组:空间复杂度 O(m)O(m),扫描某个点的出边最坏为 O(m)O(m),遍历整图最坏为 O(nm)O(nm)。
  • 邻接表:建图、空间和遍历复杂度均为 O(n+m)O(n+m)。
  • 链式邻接表:建图、空间和遍历复杂度均为 O(n+m)O(n+m)。
  • 链式前向星:建图、空间和遍历复杂度均为 O(n+m)O(n+m)。