链式前向星是一种在算法竞赛中常用的图存储方式，在空间占用和时间消耗上都比较中庸，使用比较广泛。本文以下面的无权图为例。
它的邻接矩阵表示如下：
| INF | INF | 1 | INF | 1 | 1 |
| INF | INF | INF | INF | 1 | 1 |
| INF | INF | INF | 1 | 1 | INF |
| INF | INF | INF | INF | INF | INF |
| INF | INF | INF | INF | INF | 1 |
| INF | INF | INF | INF | INF | INF |
用边表示如下，这也是更常见的输入方式：
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| From | 0 | 2 | 0 | 1 | 4 | 2 | 0 | 1 |
| To | 2 | 4 | 5 | 4 | 5 | 3 | 4 | 5 |
前置知识：前向星
前向星和链式前向星很相似（毕竟链式前向星就是基于它改进而来的）。
前向星需要一次排序，使所有边按照起点编号升序排序，同起点的边放在一起，顺序不限。
输入完毕的前向星使用三个数组，即to、head和len来存储图的基本信息。
to数组
to数组长度为边的数目，下标对应的是边的编号（不管题里给没给，这里重新设定），分别存储每条边的终点。对于边的输入，相当于以起点排序之后，终点这个数组。对于上图，to数组内容如下：
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Value | 2 | 4 | 5 | 4 | 5 | 3 | 4 | 5 |
上表中，有相同颜色的值，代表这一部分的起点相同。
去掉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数组如下图所示：
| Index | 0 | 1 | 2 | 3 | 4 |
head | 0 | 3 | 5 | -1 | 7 |
len | 3 | 2 | 2 | 0 | 1 |
比如，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数组和上面的比较相似：
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| to | 2 | 4 | 5 | 4 | 5 | 3 | 4 | 5 |
可以看到并没有按起点进行排序，其中的奇妙之处在于next数组。
next数组
next数组长度为边数，下标对应边的编号，值的含义是在to数组中下一条起点相同的边的编号，-1代表这条边已经是最后一条同起点的边了（如果边的下标从1开始，也可以为0）。依靠这个数组，可以实现to数组中同起点边的从前向后跳转。
上图的next数组如下：
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
next | 2 | 5 | 6 | 7 | -1 | -1 | -1 | -1 |
同一起点的边均已标上相同的颜色，方便查找。
例如，从0找起点同为x的边（这里我们还不知道x是多少，也不能确定是不是第一个值）：
- 在to[0]找到(x,2)，下一个下标是2；
- 在to[2]找到(x,5)，下一个下标是6；
- 在to[6]找到(x,4)，下一个下标是-1，代表已经没有同起点的边了。
当然，后来查图可以发现这是起点为0的三条边。
head数组
这里的head数组和之前那个基本完全一样，只不过它代表的是一个链的开始，而不是像前向星一样，一个区间的开始。同时由于链式前向星的无序性，它所构建的head数组和前向星并不太一样。
上图的head数组如下：
| Index | 0 | 1 | 2 | 3 | 4 |
head | 0 | 3 | 1 | -1 | 4 |
由于没有len的限制，只能从一条链上走下去，没有当作起点的结点当然就不能给予一个正常的head。
图解
图解如下：
上图用不同的颜色区分了不同的起点，下方表格之下的曲线代表了利用next数组的跳转过程，最终结果与输入完全相同。
实际使用中，如果需要带权图，只需要再新建一个weight数组即可。
参考文献
This content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.
评论