链式前向星介绍以及原理

1 链式前向星

1.1 简介

链式前向星可用于存储图，本质上是一个静态链表。

一般来说，存储图常见的两种方式为：

• 邻接矩阵
• 邻接表

邻接表的实现一般使用数组实现，而链式前向星就是使用链表实现的邻接表。

1.2 出处

出处可参考此处。

2 原理

链式前向星有两个核心数组：

• pre数组：存储的是边的前向链接关系
• last数组：存储的是某个点最后一次出现的边的下标

感觉云里雾里对吧，可以看看下面的详细解释。

2.1 pre数组

pre数组存储的是一个链式的边的前向关系，下标以及取值如下：

• pre数组的下标：边的下标
• pre数组的值：前向边的下标，如果没有前向边，取值-1

这里的前向边是指，如果某个点，作为起始点，已经出现过边x，那么，遍历到以该点作为起始点的下一条边y时，边y的前向边就是边x。

更新pre数组的时候，会遍历每一条边，更新该边对应的前向边。

比如，输入的有向边如下：

n=6 // 顶点数
[[0,1],[1,3],[3,5],[2,4],[2,3],[0,5],[0,3],[3,4]] // 边

那么：

• 对于第一条边，下标为0，那么会更新pre[0]的值，边为0->1，而起始点点0还没有出现过前向边，那么pre[0]=-1。这样就建立了边0->-1的一个链接关系，也就是说，对于起始点点0，它只有边0这一条边
• 对于第二条边，下标为1，那么会更新pre[1]的值，边为1->3，而起始点点1还没有出现过前向边，那么pre[1]=-1。这样就建立了边1->-1的一个链接关系，也就是说，对于起始点点1，它只有边1这一条边
• 对于第三条边，下标为2，那么会更新pre[2]的值，边为3->5，而起始点点3还没有出现过前向边，那么pre[2]=-1。这样就建立了边2->-1的一个链接关系，也就是说，对于起始点点3，它只有边2这一条边
• 对于第四条边，下标为3，那么会更新pre[3]的值，边为2->4，而起始点点2还没有出现过前向边，那么pre[3]=-1。这样就建立了边3->-1的一个链接关系，也就是说，对于起始点点2，它只有边3这一条边
• 对于第五条边，下标为4，那么会更新pre[4]的值，边为2->3，而起始点点2，已经出现过一条边了，该边的下标是3，也就是前向边为3，那么就会更新pre[4]为前向边的值，也就是pre[4]=3。这样，就建立了边4->3->-1的一个链接关系，也就是对于起始点点2来说，目前有两条边，一条是边4，一条是边3
• 对于第六条边，下标为5，那么会更新pre[5]的值，边为0->5，而起始点点0，已经出现过一条边了，该边的下标是边0，也就是前向边为0，那么就会更新pre[5]为前向边的值，也就是pre[5]=0。这样，就建立了边5->0->-1的一个链接关系，也就是对于起始点点0来说，目前有两条边，一条是边5，一条是边0
• 对于第七条边，下标为6，那么会更新pre[6]的值，边为0->3，而起始点点0，已经出现过不止一条边了，最后一次出现的边为边5，也就是前向边为5，那么就会更新pre[6]为前向边的值，也就是pre[6]=5。这样，就建立了边6->5->0->-1的一个链接关系，也就是对于起始点点0来说，已经有三条边了，一条是边6，一条是边5，一条是边0
• 对于第八条边，下标为7，那么会更新pre[7]的值，边为3->4，而起始点点3，已经出现过一条边了，该边的下标是边2，也就是前向边为2，那么就会更新pre[7]为前向边的值，也就是pre[7]=2。这样，就建立了边7->2->-1的一个链接关系，也就是对于起始点点3来说，目前有两条边，一条是边7，一条是边2

这样，边的链接关系就建立下来了：

点 边的链接关系(边的下标)
0  6->5->0->-1
1  1->-1
2  4->3->-1
3  7->2->-1
4  -1
5  -1

2.2 last数组

last数组存储的是最后一次出现的前向边的下标，下标以及取值如下：

• last数组的下标：点
• last数组的值：最后一次出现的前向边的下标

last数组会将所有值初始化为-1，表示所有的点在没有遍历前都是没有前向边的。

使用上面的数据举例：

n=6 // 顶点数
[[0,1],[1,3],[3,5],[2,4],[2,3],[0,5],[0,3],[3,4]] // 边

last数组会与pre数组一起在遍历边的时候更新：

• 遍历到第一条边：下标为0，边为0->1，那么会更新以0为起始点的前向边的值，也就是自己，last[0]=0。然后，如果下一次遍历到了以0为起始点的边，比如0->5，那么0->5的前向边就是边0，而边0就存储在last[0]中，下次需要的时候直接取last[0]即可
• 遍历到第二条边：下标为1，边为1->3，那么会更新以1为起始点的最后一次出现的前向边的值，也就是last[1]=1
• 遍历到第三条边：下标为2，边为3->5，那么会更新以3为起始点的最后一次出现的前向边的值，也就是last[3]=2
• 遍历到第四条边：下标为3，边为2->4，那么会更新以2为起始点的最后一次出现的前向边的值，也就是last[2]=3
• 遍历到第五条边：下标为4，边为2->3，那么会更新以2为起始点的最后一次出现的前向边的值，也就是last[2]=4
• 遍历到第六条边：下标为5，边为0->5，那么会更新以0为起始点的最后一次出现的前向边的值，也就是last[0]=5
• 遍历到第七条边：下标为6，边为0->3，那么会更新以0为起始点的最后一次出现的前向边的值，也就是last[0]=6
• 遍历到第八条边：下标为7，边为3->4，那么会更新以3为起始点的最后一次出现的前向边的值，也就是last[3]=7

在遍历每条边的时候，会先从last数组取值并赋给pre去生成链接关系，然后更新last数组中对应起始点的值为当前的边的下标。

3 代码

3.1 生成数组

生成last以及pre数组：

public class Solution {private int[] pre;private int[] last;private void buildGraph(int n, int[][] edge) {int edgeCount = edge.length;pre = new int[edgeCount];last = new int[n];Arrays.fill(last, -1);for (int i = 0; i < edgeCount; i++) {int v0 = edge[i][0];pre[i] = last[v0];last[v0] = i;}}
}

pre的范围与边数有关，而last的范围与点数有关。一开始需要初始化last数组为-1，然后遍历每一条边：

• 遍历边时仅需要知道起始点即可，因为终点可以通过边的下标获取到，不需要存储
• 遍历时首先更新pre数组为最后一次出现的前向边的下标，也就是对应起始点的last数组的值
• 最后更新last数组，对应起始点的值更新为当前边的下标

3.2 遍历

public class Solution {private int[] pre;private int[] last;private void visit(int n, int[][] edge) {for (int i = 0; i < n; i++) {System.out.println("当前顶点:" + i);for (int lastEdge = last[i]; lastEdge != -1; lastEdge = pre[lastEdge]) {System.out.println(edge[lastEdge][0] + "->" + edge[lastEdge][1]);}}}
}

遍历从点开始，首先通过last数组取得最后一条出现的前向边的下标，然后遍历该边，最后通过pre数组更新前向边，也就是对链接关系进行遍历。

3.3 完整测试代码

import java.util.Arrays;public class Solution {private int[] pre;private int[] last;private void buildGraph(int n, int[][] edge) {int edgeCount = edge.length;pre = new int[edgeCount];last = new int[n];Arrays.fill(last, -1);for (int i = 0; i < edgeCount; i++) {int v0 = edge[i][0];pre[i] = last[v0];last[v0] = i;}}private void visit(int n, int[][] edge) {for (int i = 0; i < n; i++) {System.out.println("当前顶点:" + i);for (int lastEdge = last[i]; lastEdge != -1; lastEdge = pre[lastEdge]) {System.out.println(edge[lastEdge][0] + "->" + edge[lastEdge][1]);}}}public void build() {int n = 6;int[][] edge = {{0, 1}, {1, 3}, {3, 5}, {2, 4}, {2, 3}, {0, 5}, {0, 3}, {3, 4}};buildGraph(n, edge);visit(n, edge);}
}

输出：

当前顶点:0
0->3
0->5
0->1
当前顶点:1
1->3
当前顶点:2
2->3
2->4
当前顶点:3
3->4
3->5
当前顶点:4
当前顶点:5

可以看到输出的顺序与edge数组是相反的，比如edge数组中的以0为起始点的边的顺序为0->1,0->5,0->3，而输出顺序为0->3,0->5,0->1，这是因为pre的前向链接关系，生成pre数组的时候，采用的是类似链表中的“头插法”生成。

如果想要和原来的顺序保持一致，可以将edge数组反转再生成pre和last数组：

private void buildGraph(int n, int[][] edge) {int edgeCount = edge.length;int[][] reverseEdge = new int[edgeCount][2];for (int i = 0; i < edgeCount; i++) {reverseEdge[i] = edge[edgeCount - i - 1];}pre = new int[edgeCount];last = new int[n];Arrays.fill(last, -1);for (int i = 0; i < edgeCount; i++) {int v0 = reverseEdge[i][0];pre[i] = last[v0];last[v0] = i;}
}

然后遍历edge数组的时候也需要反转：

private void visit(int n, int[][] edge) {int edgeCount = edge.length;int[][] reverseEdge = new int[edgeCount][2];for (int i = 0; i < edgeCount; i++) {reverseEdge[i] = edge[edgeCount - i - 1];}for (int i = 0; i < n; i++) {System.out.println("当前顶点:" + i);for (int lastEdge = last[i]; lastEdge != -1; lastEdge = pre[lastEdge]) {System.out.println(reverseEdge[lastEdge][0] + "->" + reverseEdge[lastEdge][1]);}}
}

测试代码不变：

public void build() {int n = 6;int[][] edge = {{0, 1}, {1, 3}, {3, 5}, {2, 4}, {2, 3}, {0, 5}, {0, 3}, {3, 4}};buildGraph(n, edge);visit(n, edge);
}

输出：

当前顶点:0
0->1
0->5
0->3
当前顶点:1
1->3
当前顶点:2
2->4
2->3
当前顶点:3
3->5
3->4
当前顶点:4
当前顶点:5

可以看到输出顺序和edge对应的边的顺序一致了。

4 疑问

4.1 为什么叫pre数组而不是next数组

笔者看到网上的文章很多都是如下三个数组：

• head[u]数组：表示以u作为起点的第一条边的编号
• next[cnt]数组：表示编号为cnt的边的下一条边，这条边与cnt同一个起点
• to[cnt]数组：表示编号为cnt的边的终点

其中to[cnt]数组在本篇文章中没有实现，因为已经有edge数组存储了。

head[u]数组，相当于本篇文章中的last数组，而next[cnt]数组，相当于本篇文章中的pre数组。

那么为什么取不同的名字？

只是笔者认为，从自己的角度出发，这样好比较理解。如果还是觉得难理解，可以到文末的参考链接处看一下其他文章。

4.2 这个东西到底有什么用

链式前向星能做的题目，一般来说邻接表也能做。链式前向星，不是用来帮你AC题目来的，不是说某道题非得用它。它是用来帮助你在AC的基础上，进一步提高效率。链式前向星是一种优化手段，它只是帮助你优化，而不是学习了它，就能AC题目。

5 参考

• Malash’s Blog-链式前向星及其简单应用
• CSDN-链式前向星–最通俗易懂的讲解
• 知乎-链式前向星