图的存储

约定¶

\(n\) 指代图的点数，\(m\) 指代图的边数，\(d^{+}(u)\) 指代点 \(u\) 的出度。

邻接矩阵¶

方法¶

使用二维数组 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)\)

应用¶

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

链式前向星(Chain Forward Star)¶

【图论02】动画说图的三种保存方式 降低理解门槛 邻接表 链式前向星 邻接矩阵_哔哩哔哩_bilibili

实现¶

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

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

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

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

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

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

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

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

    edge[cnt].to = v;
    edge[cnt].next = head[u];
    edge[cnt].w = w;
    head[u] = cnt;
}

复杂度¶

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

应用¶

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

优点是边都是带编号的。