直接存边
方法
使用一个数组来存边，数组中的每个元素都包含一条边的起点与终点（带边权的图还包含边权）。（或者使用多个数组分别存起点，终点和边权。）
代码实现
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
| struct Edge {
int u, v;
};
const int N = 1e5;
int n, m;
Edge arr[N];
bool vis[N];
bool find_edge(int u, int v) {
for (int i = 1; i <= m; i++) {
if (arr[i].u == u && arr[i].v == v) return true;
}
return false;
}
void dfs(int u) {
if (vis[u]) return;
vis[u] = true;
for (int i = 1; i <= m; i++) {
if (arr[i].u == i) dfs(arr[i].v);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> arr[i].u >> arr[i].v;
}
|
复杂度
查询是否存在某条边：O(m)。
遍历一个点的所有出边：O(m)。
遍历整张图：O(nm)。
空间复杂度：O(m)。
应用
由于直接存边的遍历效率低下，一般不用于遍历图。
在 Kruskal 算法 中，由于需要将边按边权排序，需要直接存边。
在有的题目中，需要多次建图（如建一遍原图，建一遍反图），此时既可以使用多个其它数据结构来同时存储多张图，也可以将边直接存下来，需要重新建图时利用直接存下的边来建图。
邻接矩阵
方法
使用一个二维数组 arr 来存边，其中 arr[u][v] 为 1 表示存在 u 到 v 的边，为 0 表示不存在。如果是带边权的图，可以在 arr[u][v] 中存储 u 到 v 的边的边权。
代码实现
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
| const int N = 1e5;
int n, m;
int arr[N][N];
int vis[N];
bool find_edge(int u, int v) {
return arr[u][v] != 0;
}
void dfs(int u) {
if (vis[u]) return;
vis[u] = 1;
for (int i = 1; i <= n; i++) {
if (arr[u][i]) dfs(i);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
arr[u][v] = w;
}
}
|
复杂度
查询是否存在某条边：O(1)。
遍历一个点的所有出边：O(n)。
遍历整张图：O(n^2)。
空间复杂度：O(n^2)。
应用
邻接矩阵只适用于没有重边（或重边可以忽略）的情况。
其最显著的优点是可以 O(1) 查询一条边是否存在。
由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。
邻接表
方法
使用一个支持动态增加元素的数据结构构成的数组，如 vector<int> arr[n + 1] 来存边，其中 adj[u] 存储的是点 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
| const int N = 1e5;
int n, m;
vector<int> arr[N];
int vis[N];
int find_edge(int u, int v) {
for (auto to : arr[u]) if (to == v) return true;
return false;
}
void dfs(int u) {
if (vis[u]) return;
vis[u] = 1;
for (auto v : arr[u]) {
dfs(v);
}
}
int main() {
cin >> n >> m;
for (int i = 0; i <= m; i++) {
int u, v;
cin >> u >> v;
arr[u].emplace_back(v);
}
}
|
复杂度
查询是否存在 u 到 v 的边：O(d^+(u))（如果事先进行了排序就可以使用 二分查找 做到 O(log(d^+(u)))）。
遍历点 u 的所有出边：O(d^+(u))。
遍历整张图：O(n+m)。
空间复杂度：O(m)。
应用
存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。
尤其适用于需要对一个点的所有出边进行排序的场合。
链式前向星
方法
本质上是用链表实现的邻接表。
代码实现
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
| const int N = 1e5;
struct Edge {
int to;
int w;
int next;
} arr[N << 1];
int n, m;
int head[N], index;
int vis[N];
void init() {
for (int i = 1; i < N; i++) {
head[i] = -1;
}
}
inline void add_edge(int u, int v, int w) {
arr[index].to = v;
arr[index].w = w;
arr[index].next = head[u];
head[u] = index++;
}
void dfs(int u) {
if (vis[u]) return;
vis[u] = 1;
for (int i = head[u]; i != -1; i = arr[i].next) {
dfs(arr[i].to);
}
}
int main() {
cin >> n >> m;
init();
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
add_edge(u, v, w);
}
}
|
复杂度
查询是否存在 u 到 v 的边：O(d^+(u))。
遍历点 u 的所有出边：O(d^+(u))。
遍历整张图：O(n+m)。
空间复杂度：O(m)。
应用
存各种图都很适合，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序。
优点是边是带编号的，有时会非常有用，而且如果 cnt 的初始值为奇数，存双向边时 i ^ 1 即是 i 的反边（常用于 网络流）。
微信
支付宝