链式前向星:一种图的存储方式
本文最后更新于 343 天前,其中的信息可能已经有所发展或是发生改变。

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

它的邻接矩阵表示如下:

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和len数组

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

Index01234
head031-14
head数组

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

图解

图解如下:

链式前向星图解

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

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


参考文献

评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇