归档157

834 字

4 分钟

图的存储

2025-11-29

数据结构与算法

图的存储#

图论题的第一步通常不是跑算法，而是先把图存起来。

不同存储方式适合不同场景。常见方式有：

邻接矩阵
边集数组
邻接表
链式前向星

1、先理解图里的基本元素#

图由点和边组成。

如果有一条边：

1
a -> b，权重为 c

那么存图时至少要记录：

1
起点 a
2
终点 b
3
权重 c

如果是无向图，一条边 a - b 通常要存两次：

1
a -> b
2
b -> a

2、邻接矩阵#

邻接矩阵用二维数组存边：

1
int g[N][N];

如果 g[a][b] = c，表示从 a 到 b 有一条权重为 c 的边。

初始化时一般写：

1
memset(g, 0x3f, sizeof g);
2
for (int i = 1; i <= n; i++) g[i][i] = 0;

加边：

1
g[a][b] = min(g[a][b], c);

邻接矩阵的优点是查询两点之间是否有边很快，O(1)。

缺点是空间复杂度是 O(n^2)，点数大时开不下。

3、边集数组#

边集数组就是把每条边直接存成一个结构体：

1
struct Edge {
2
    int a, b, w;
3
};
4

5
vector<Edge> edges;

加边：

1
edges.push_back({a, b, w});

这种写法适合 Kruskal 最小生成树，因为 Kruskal 需要把所有边拿出来排序。

4、vector 邻接表#

如果要经常遍历某个点的所有出边，可以用邻接表：

1
vector<pair<int, int>> g[N];

其中：

1
g[a] 存从 a 出发的所有边
2
pair 的 first 是终点，second 是权重

加边：

1
g[a].push_back({b, c});

遍历：

1
for (auto item : g[a]) {
2
    int b = item.first;
3
    int c = item.second;
4
}

这种写法直观，适合学习和一般题目。

5、链式前向星#

竞赛模板里经常使用链式前向星，本质上是用数组模拟邻接表。

1
const int N = 100010;
2
const int M = 200010;
3

4
int h[N], e[M], w[M], ne[M], idx;

含义：

1
h[a]：点 a 的第一条边编号
2
e[i]：第 i 条边的终点
3
w[i]：第 i 条边的权重
4
ne[i]：与第 i 条边同起点的下一条边编号
5
idx：当前边编号

初始化：

1
memset(h, -1, sizeof h);

加边：

1
void add(int a, int b, int c) {
2
    e[idx] = b;
3
    w[idx] = c;
4
    ne[idx] = h[a];
5
    h[a] = idx++;
6
}

遍历点 a 的所有出边：

1
for (int i = h[a]; i != -1; i = ne[i]) {
2
    int b = e[i];
3
    int c = w[i];
4
}

6、完整链式前向星模板#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int N = 100010;
5
const int M = 200010;
6

7
int n, m;
8
int h[N], e[M], w[M], ne[M], idx;
9

10
void add(int a, int b, int c) {
11
    e[idx] = b;
12
    w[idx] = c;
13
    ne[idx] = h[a];
14
    h[a] = idx++;
15
}
16

17
int main() {
18
    cin >> n >> m;
19
    memset(h, -1, sizeof h);
20

21
    while (m--) {
22
        int a, b, c;
23
        cin >> a >> b >> c;
24
        add(a, b, c);
25
    }
26

27
    for (int a = 1; a <= n; a++) {
28
        cout << a << ":";
29
        for (int i = h[a]; i != -1; i = ne[i]) {
30
            cout << " -> " << e[i] << "(" << w[i] << ")";
31
        }
32
        cout << endl;
33
    }
34

35
    return 0;
36
}

7、怎么选择存图方式#

1
点数小、要快速查边：邻接矩阵
2
要给所有边排序：边集数组
3
要遍历每个点的出边：邻接表
4
追求数组模板和性能：链式前向星

8、原图笔记#

下面保留原来的图示，方便对照复习。

邻接矩阵#

边集数组#

邻接表#

链式邻接表#

链式前向星#

总结#

图的存储方式会影响后面算法的写法。学习 Dijkstra、Prim、拓扑排序这类算法时，建议优先掌握链式前向星，因为它和竞赛模板结合得最紧。

文章分享

如果这篇文章对你有帮助，欢迎分享给更多人！