图的存储

方法#

使用二维数组 adj 存边，其中 adj[u][v] 为 1 代表存在从 $u$ 到 $v$ 的边，0 表示不存在。如果是带权图，可以存储权重。

复杂度#

查询是否存在某条边：$O(1)$
遍历一个点的所有出边：$O(n)$
遍历整张图：$O(n^2)$
空间复杂度：$O(n^2)$

应用#

邻接矩阵只适用于没有重边（或重边可以忽略）的情况。
优点是可以以 $O(1)$ 查询边的存在性。
缺点是空间复杂度高，在稀疏图上空间浪费严重。

方法#

在邻接表的表示中，对于图中的每个顶点，将保存所有其它与之相连的顶点（即“邻接表”）。
在实现上使用一个支持动态增加元素的数据结构构成的数组，如 vector<int> adj[n + 1] 来存边，其中 adj[u] 存储的是点 $u$ 的所有出边的相关信息(终点，边权)。

复杂度#

查询是否存在从 $u$ 到 $v$ 的边：$O(d^+(u))$
遍历 $u$ 的所有出边：$O(d^+(u))$
遍历整张图：$O(n+m)$
空间复杂度：$O(m)$

应用#

具有通用性，特别是需要对一个点的所有出边进行排序的场合。

实现#

以边为基本单位，记录每条边的目标点。

链式前向星是一种静态链表存储，用边集数组和邻接表相结合，可以快速访问一个顶点的所有邻接点。

链式前向星存储包括两种结构：

1. 头结点数组：head[]，head[i]存以i为起点的最后一条边的下标（在edge[]中的下标）。

2. 边数组：edge[]，edge[i] 表示第 i 条边。

1
struct node {
2
    int to; // 第 i 条边的目标点
3
    int w; // 第 i 条边的边权
4
    int next; // 第 i 条边同起点的下一跳边的位置
5
} edge[maxn]
6

7
// head[u]和cnt起始设置为-1
8
int head[maxn] = {-1, ..., -1}; // 头结点数组, 最近一输入的以 i 为起点的边在 edge[] 中的下标
9
int cnt = -1;
10

11
void add(int u, int v, int w) {
12
    ++cnt;
13

14
    edge[cnt].to = v;
15
    edge[cnt].next = head[u];
16
    edge[cnt].w = w;
17
    head[u] = cnt;
18
}

复杂度#

查询是否存在从 $u$ 到 $v$ 的边：$O(d^+(u))$
遍历 $u$ 的所有出边：$O(d^+(u))$
遍历整张图：$O(n+m)$
空间复杂度：$O(m)$

应用#

存各种图都很适合，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序。

优点是边都是带编号的。