链式前向星是一种在算法竞赛中常用的图存储方式，在空间占用和时间消耗上都比较中庸，使用比较广泛。本文以下面的无权图为例。

它的邻接矩阵表示如下：

用边表示如下，这也是更常见的输入方式：

前置知识：前向星

前向星和链式前向星很相似（毕竟链式前向星就是基于它改进而来的）。

前向星需要一次排序，使所有边按照起点编号升序排序，同起点的边放在一起，顺序不限。

输入完毕的前向星使用三个数组，即 to、head 和 len 来存储图的基本信息。

to 数组

to 数组长度为边的数目，下标对应的是边的编号（不管题里给没给，这里重新设定），分别存储每条边的终点。对于边的输入，相当于以起点排序之后，终点这个数组。对于上图，to 数组内容如下：

前向星 to 数组

上表中，有相同颜色的值，代表这一部分的起点相同。

去掉 from 数组之后，孤零零的 to 数组当然难以理解有什么用处。但我们还需要 from 数组来生成 head 和 len。

head、len 数组

head 和 len 数组长度为结点的数目，这两个数组的下标对应的是结点的编号。

to 数组因已经过按起点的排序，实际上按起点被划分为了一个个区间。如上图，起点为 0 的 to** 下标 **（而不是 to 值）为 0、1 和 2，起点为 1 的 to 下标有 3、4，起点为 2 的 to 下标为 5、6，起点为 3 没有对应 to 下标，起点为 4 对应的 to 下标有 7。

因此，我们就需要 head 和 len 两个数组，分别存储某个结点对应的下标区间范围，head[i] 存储的是结点 i 对应下标区间的起始位置，而 len[i] 存储结点 i 对应下标区间长度。上图所对应的 head 和 len 数组如下图所示：

比如，head[0]==0&&len[0]==3 代表了起点为 0 的边范围是从第 0 个开始，有 3 个，查找对应的 to 数组得到各自终点，也就是有 (0,2)(0,4)(0,5) 三条边。而 head[3]==-1 是为了表示以 3 为起点没有对应的边，其实它的值是多少并不重要，重要的是长度为 0。

这样我们就描述了按照起点划分的区间，进而描述了所有的边，“前向星” 就是这么一个东西。

链式前向星

因为普通的前向星需要排序，没有那么方便，所以就要找一种并不需要同一起点的边连续的结构，方便存储。链式前向星就是这么一种存储方式，它所谓的 “链式” 并不是使用链表来存储，而是每条边在数组中存储的的位置不固定，要靠一个数组来指导跳转，可以理解为数组模拟链表。

链式前向星更难理解，但理解之后写起来会容易不少。

它由 head、next 和 to 数组组成。

to 数组

这里的 to 数组和上面的比较相似：

链式前向星 to 数组

可以看到并没有按起点进行排序，其中的奇妙之处在于 next 数组。

next 数组

next 数组长度为边数，下标对应边的编号，值的含义是在 to 数组中下一条起点相同的边的编号，-1 代表这条边已经是最后一条同起点的边了（如果边的下标从 1 开始，也可以为 0）。依靠这个数组，可以实现 to 数组中同起点边的从前向后跳转。

上图的 next 数组如下：

同一起点的边均已标上相同的颜色，方便查找。

例如，从 0 找起点同为 x 的边（这里我们还不知道 x 是多少，也不能确定是不是第一个值）：

1. 在 to[0] 找到 (x,2)，下一个下标是 2；
2. 在 to[2] 找到 (x,5)，下一个下标是 6；
3. 在 to[6] 找到 (x,4)，下一个下标是 - 1，代表已经没有同起点的边了。

当然，后来查图可以发现这是起点为 0 的三条边。

head 数组

这里的 head 数组和之前那个基本完全一样，只不过它代表的是一个链的开始，而不是像前向星一样，一个区间的开始。同时由于链式前向星的无序性，它所构建的 head 数组和前向星并不太一样。

上图的 head 数组如下：

head 数组

由于没有 len 的限制，只能从一条链上走下去，没有当作起点的结点当然就不能给予一个正常的 head。

图解

图解如下：

上图用不同的颜色区分了不同的起点，下方表格之下的曲线代表了利用 next 数组的跳转过程，最终结果与输入完全相同。

实际使用中，如果需要带权图，只需要再新建一个 weight 数组即可。

参考文献

• 秘技 · 反复横跳！在下 链式前向星 - 知乎 (zhihu.com)
• 链式前向星 - 避风港 (kindkidll.com)
• 图的存储 - OI Wiki (oi-wiki.org)