图的存储结构 - 链式前向星、邻接表

图的定义和术语总结

图按照有无方向分为有向图和无向图。有向图由顶点和弧构成。无向图由顶点和边构成。弧有弧尾和弧头之分。
无向图顶点边数叫做度，有向图顶点分为入度和出度。

图的存储结构

图的存储只影响遍历方式和效率。

邻接矩阵（Adjacency Matrix）

简单、好理解。但点的数量不能太多，n ≤ 1000 n≤1000n≤1000。
在无向图中，顶点v i v_ivi​的度为在邻接矩阵中第i ii行（或第i ii列）的元素之和。
在有向图中，顶点v i v_ivi​的出度为在邻接矩阵中第i ii行的元素之和，顶点v i v_ivi​的入度为在邻接矩阵中第i ii列的元素之和。
在带权图中，一般初始化为∞ \infty∞，表示没有边。
n nn个顶点和e ee条边的无向图的创建，时间复杂度为O ( n + n 2 + e ) O(n+n^2+e)O(n+n2+e)，其中初始化邻接表耗费O ( n 2 ) O(n^2)O(n2)。

在无向图中，还有一种「半矩阵」的存储方式，用上三角（或下三角）+ 主对角线 压缩存储的一维数组方式。
一个n × n n\times nn×n的邻接矩阵可以被压缩到n ( n + 1 ) 2 \frac{n(n+1)}{2}2n(n+1)​个元素。

邻接表（Adjacency List）

上述邻接矩阵对于边数较少顶点较多的图会产生极大浪费。
我们把数组与链表相结合的存储方式成为邻接表。
邻接表一般用ArrayList<ArrayList<Integer>> 维护。最常用。
n nn个顶点和e ee条边的无向图的创建，时间复杂度为O ( n + e ) O(n+e)O(n+e)。

链式前向星

静态版的邻接表，时空效率更极致。
本质上是用链表实现的邻接表，从点映射到第一条边，再在n e x t nextnext数组上跳跃。这个链表使用头插法维护的。
h e a d headhead数组：起点 → 映射 第一条边 起点 \xrightarrow{\text{映射}} 第一条边起点映射​第一条边。
n e x t nextnext数组，边 → 映射 当前边的后继 边 \xrightarrow{\text{映射}} 当前边的后继边映射​当前边的后继。
t o toto数组：边 → 映射 当前边的终点 边 \xrightarrow{\text{映射}} 当前边的终点边映射​当前边的终点。
核心代码如下：

// 把握住头插法的流程// head[u] 和 cnt 的初始值为 -1publicstaticvoidadd(intu,intv,intw){next[++cnt]=head[u];head[u]=cntto[cnt]=v;weight[cnt]=w;}// 遍历所有点for(intu=1;u<=n;u++){System.out.print(u+"(邻居、边权) : ");// 遍历 u 的出边for(inti=head[u];i!=-1;i=next[i]){// c++ 可以用 ~i 用于表示 i != -1System.out.print("("+to[i]+","+weight[i]+") ");}System.out.println();}

h e a d headhead数组长度为点的数量
n e x t 、 t o 、 w e i g h t next、to、weightnext、to、weight数组长度为边的数量，如果是无向图则需要边的数量x2。

#atom