乐趣区

关于链表:链式前向星介绍以及原理

jiezi

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- 链式前向星 – 最通俗易懂的解说
  • 知乎 - 链式前向星
退出移动版