目录

本文目录

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

图论简介

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

邻接矩阵

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

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

如果给定$m$条边，也很简单，枚举所有边

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(n^2)$

空间复杂度：$O(n^2)$

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

边集数组

我们使用一个结构体数组来存储$起点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(m)$

应用：常用于Kruskal算法中，按边权排序存边

邻接表

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

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

实现代码：

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)$

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

链式邻接表

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

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

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)$

应用：可以应用到各种图，并且可以处理反向边

链式前向星

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

$edge$数组是一个边集，存边的信息

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)$

应用：可以用于所有图，可以处理反向边

总结与常见问题

常见问题

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

复杂度分析

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