「学习笔记」存图

我们既然正在学习 图论 ，那么我们就 必须 掌握几种 存图方式 。

PS:本文记点 \(u\) 的 出度 为 \(degree^{+(u)}\)

1. 直接存图

用一个 结构体数组 \(edge_i\) 来存图，结构体中包含这条边 \((u,v,w)\) 的 源点、汇点，权值 。

显然，此方法 空间复杂度 为 \(O(m)\) ，查询某条边的时间复杂度 为 \(O(m)\) 。

2. 邻接矩阵

邻接矩阵是一种 方便且容易理解 的存图方式。

其本质是一个数组 \(grath_{i,j}\space(1\le i,j\le n)\) ，表示从点 \(i\) 到点 \(j\) 的权值。

显然，邻接矩阵的 空间复杂度 是 \(O(n^2)\) 。

如此之高的空间复杂度，只要 \(n\ge 10^4\) ， 内存就会超出限制 ，而且也不能应用在 有重边 的情况下。

但是，

在 稠密图 ( \(m\approx n^2\) ) ，下，它比 直接存图的方式更优 ，因为要查询某一条边，两者的时间复杂度分别为 \(O(m)\) 和 \(O(1)\) 。

而接下来介绍的方法，比前两者 都更优秀 。

3. 邻接表 (链式前向星)

这种方法使用一个支持动态增加元素的数据结构构成的数组， 如使用 struct edge {int v,w,nxt;} grath[MAXM]; 来存边，其中 grath[cnt] 存储的是第 \(cnt\) 条边的相关信息 (去向、权等)。

而 链式前向星 就是用 链表 实现的 邻接表 。

此方式的时空复杂度 极其优秀：

查询是否存在边 \((u,v)\) ： \(O(degree^{+(u)})\) ，可优化到 \(O(\log(degree^{+(u)}))\)

遍历点 \(u\) 的所有出边 (即以点 \(u\) 为源点的边)： \(O(degree^{+(u)})\)

遍历整张图： \(O(n+m)\)

空间复杂度： \(O(m)\)

总结：

如果是在 稠密图且没有重边 的情况下，可以使用 邻接矩阵 。

如果要像 \(Kruskal算法\) 一样按照 边权大小 进行排序，则 必须使用直接存图 。

一般情况下，请使用 邻接表 或 链式前向星 。