湖南省建设监理协会网站,网站开发自学,网站开通flash,保定网站推广公司1 链式前向星
1.1 简介
链式前向星可用于存储图#xff0c;本质上是一个静态链表。
一般来说#xff0c;存储图常见的两种方式为#xff1a;
邻接矩阵邻接表
邻接表的实现一般使用数组实现#xff0c;而链式前向星就是使用链表实现的邻接表。
1.2 出处
出处可参考此…1 链式前向星
1.1 简介
链式前向星可用于存储图本质上是一个静态链表。
一般来说存储图常见的两种方式为
邻接矩阵邻接表
邻接表的实现一般使用数组实现而链式前向星就是使用链表实现的邻接表。
1.2 出处
出处可参考此处。
2 原理
链式前向星有两个核心数组
pre数组存储的是边的前向链接关系last数组存储的是某个点最后一次出现的边的下标
感觉云里雾里对吧可以看看下面的详细解释。
2.1 pre数组
pre数组存储的是一个链式的边的前向关系下标以及取值如下
pre数组的下标边的下标pre数组的值前向边的下标如果没有前向边取值-1
这里的前向边是指如果某个点作为起始点已经出现过边x那么遍历到以该点作为起始点的下一条边y时边y的前向边就是边x。
更新pre数组的时候会遍历每一条边更新该边对应的前向边。
比如输入的有向边如下
n6 // 顶点数
[[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 -12.2 last数组
last数组存储的是最后一次出现的前向边的下标下标以及取值如下
last数组的下标点last数组的值最后一次出现的前向边的下标
last数组会将所有值初始化为-1表示所有的点在没有遍历前都是没有前向边的。
使用上面的数据举例
n6 // 顶点数
[[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-链式前向星–最通俗易懂的讲解知乎-链式前向星
