链式前向星:一种图的存储方式

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

图例
图例

它的邻接矩阵表示如下:

INFINF1INF11
INFINFINFINF11
INFINFINF11INF
INFINFINFINFINFINF
INFINFINFINFINF1
INFINFINFINFINFINF

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

Index01234567
From02014201
To24545345

前置知识:前向星

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

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

输入完毕的前向星使用三个数组,即 toheadlen 来存储图的基本信息。

to 数组

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

Index01234567
Value24545345

前向星 to 数组

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

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

headlen 数组

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

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

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

Index01234
head035-17
len32201

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

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

链式前向星

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

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

它由 headnextto 数组组成。

to 数组

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

Index01234567
to24545345

链式前向星 to 数组

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

next 数组

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

上图的 next 数组如下:

Index01234567
next2567-1-1-1-1

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

例如,从 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 数组如下:

Index01234
head031-14

head 数组

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

图解

图解如下:

链式前向星图解

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

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


参考文献

许可证:CC BY-SA 4.0
最后更新于 2023 年 6 月 14 日 21:05