链式前向星(Linked Forward Star)是图论中用于存储图的一种边表存储结构,以静态链表的方式实现邻接表,也被称为静态邻接表。它由边集数组和头结点数组两部分组成,把同一起点的所有出边用 next 字段串成链表,从而在不使用指针的情况下快速访问某个顶点的全部邻接点。相比前向星,它省去了对边排序的步骤,相比邻接表,它的编码更简洁、额外空间开销更小,因此常被用于稀疏图的存储与遍历。[1]
定义
链式前向星是图的一种存储方式,用数组模拟链表来实现前向星的功能,在分类上属于边集数组的一种,又常被称作静态邻接表。[2][3]
它并没有改变边集数组原有的存储顺序,只是借助头结点数组建立了顶点与边之间的关联,本质上是把邻接表改写成静态链表的数组实现形式。[2][4]
原理
该结构由两类数据结构配合完成存储。边集数组 edge[] 中的每个元素代表一条边,记录三个字段:to 表示边的终点,next 表示与它起点相同的下一条边在数组中的下标,w 表示边权。头结点数组 head[] 则记录以顶点 i 为起点的第一条边在 edge[] 中的下标,通常把 head[] 全部初始化为 -1,用来表示该顶点暂时没有出边。[1][5]
插入一条边的操作是:先令新边的 next 字段等于 head[u],再让 head[u] 指向这条新边,这种写法称为头插法。用伪代码表示即 edge[++cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt。由于采用了头插法,最后读入的边会位于链首,因此遍历某顶点出边的顺序与输入顺序正好相反。[1][5]
访问某个顶点 u 的全部邻接点时,从 head[u] 出发,顺着 next 字段不断向后跳转,直到下标为 -1 为止,写成循环即 for(i=head[u]; i!=-1; i=edge[i].next)。整个过程只涉及数组下标运算,不产生动态内存分配。[1][5]
建图与遍历的代价是线性的。初始化并按上述方式依次插入全部边,总耗时为 $O(n+m)$,其中 n 为顶点数,m 为边数;而遍历某个顶点全部出边的耗时与它的出度成正比,记为 $O(TD(v_i))$。若只用链式前向星判断顶点 $v_i$ 到 $v_j$ 是否存在边,最坏情况下要走过 $v_i$ 的全部出边。
对于无向图,每读入一条边需要调用两次加边操作,分别加入 u→v 与 v→u 两条有向边。按顺序编号时,编号为 i 的边与编号为 i^1 的边互为反向边,只需一次异或运算即可定位,这一性质在网络流的实现中很方便。[1][6]
发展历程
在链式前向星出现之前,常见做法是前向星。前向星是一种特殊的边集数组,把各边按起点排序、起点相同时再按终点排序,同时用 len[i] 记录以 i 为起点的边在数组中的存储长度,用 head[i] 记录其第一个存储位置。这样能以 $O(1)$ 找到某个起点的第一条边,并以 $O(len[i])$ 走完全部出边。[5][2]
前向星的短板在于排序。若采用快速排序,仅排序一步就至少要 $O(e \log e)$ 的时间,对于时间复杂度约为 $O(ke)$(k 约为 2)的 SPFA 一类算法,这种预处理可能得不偿失。前向星的构造耗时主要来自元素之间的频繁交换。[2]
为免除排序环节,链式前向星把链表的思想引入前向星:用 head[i] 记录以 i 为起点的第一条边的存储位置,用 next[i] 记录与第 i 条边同起点的下一条边所在位置,并用 e[i] 记录该边的终点。构造过程相当于向链表中插入元素,构造的时间复杂度降为 $O(e)$,而查询效率与普通前向星一致。该结构由 Malash 提出。[2]
应用
链式前向星广泛出现在算法竞赛的图论题目中,常被视为一项基础的存图技能。它对稀疏图尤为合适,因为不必像邻接矩阵那样按顶点数平方开辟空间。[7]
在图的搜索与最短路算法中,它可用于存放稀疏图的边,配合深度优先搜索、广度优先搜索以及单源最短路径算法使用。前向星本身就适合优化稀疏图的深度优先搜索与广度优先搜索,而链式前向星沿用了同样的访问接口却没有排序开销。[2]
在网络流的最大流实现中,主流做法之一就是用链式前向星存图,并令边从偶数编号开始,使 i 与 i⊕1 互为反向边,从而快速访问反向边。此外,链式前向星也常与并查集结合,用于处理图的连通性问题。[6]
局限
链式前向星属于静态结构,边数与顶点数的规模需要在建图前确定,边集数组应按照最大可能的边数开好空间。若题目涉及双向边而数组仍按边数开辟,就会因为需要存入两倍数量的有向边而越界。[7]
由于采用头插法且遍历顺序与输入顺序相反,边输入次序的不同会导致构造出的链式前向星不同,与邻接表的表现一致;需要按特定次序访问邻接点时,要在插入后再作处理。[1]
它并不适合需要频繁判断任意两点之间是否相连的场合。仅凭链式前向星判断 $v_i$ 到 $v_j$ 是否有边,必须遍历 $v_i$ 的全部出边,代价为 $O(TD(v_i))$,而邻接矩阵在这类查询上只需常数时间。
参见
参考资料
- 链式前向星——最完美图解 [引用日期2026-10-14]
- 链式前向星及其简单应用 [引用日期2026-10-14]
- 图的储存方式，链式前向星最简单实现方式 （边集数组） [引用日期2026-10-14]
- 图是怎么存的？ [引用日期2026-10-14]
- 链式前向星 [引用日期2026-10-14]
- max-flow [引用日期2026-10-14]
- 图论的小技巧以及扩展 - 图论，其实是数学的一门分支，它以图为研究对象 [引用日期2026-10-14]