链式前向星 - (Linked) Forward Star

它是一种存图的方式，是优化过的邻接表的表达方式

定义

为了方便，我们约定 k 为点数，m 为边数。

邻接矩阵：适用于边数较多的「稠密图」使用，当边数量接近点的数量的平方，即 「m ≈ n^2」 时，可定义为「稠密图」。

邻接表：适用于边数较少的「稀疏图」使用，当边数量接近点的数量，即 「m ≈ n」 时，可定义为「稀疏图」。

代码

1
2
3
4
5
6
7
8
9
10
int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
int idx;

void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = he[a];
    he[a] = idx;
    w[idx] = c;
    idx++;
}

idx 是用来对边进行编号的，然后对存图用到的几个数组作简单解释：

  • he 数组：存储是某个节点所对应的边的集合（链表）的头结点；
  • e 数组：由于访问某一条边指向的节点；
  • ne 数组：由于是以链表的形式进行存边，该数组就是用于找到下一条边；
  • w 数组：用于记录某条边的权重为多少。

因此当我们想要遍历所有由 a 点发出的边时，可以使用如下方式：

1
2
3
for (int i = he[a]; i != -1; i = ne[i]) {
    int b = e[i], c = w[i]; // 存在由 a 指向 b 的边，权重为 c
}

自己整理的java版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.Arrays;

public class LinkedForwardStar {
    int[] head = new int[5];
    int[] edge = new int[10];
    int[] next = new int[10];
    int[] weight = new int[10];
    int tot = 0;
    LinkedForwardStar() {
        Arrays.fill(head, -1);
    }
    private void add (int a, int b, int w) {
        edge[tot] = b; // 设置边的终点
        next[tot] = head[a]; // 设置该边的下一条边
        weight[tot] = w; // 设置该边的权重
        head[a] = tot; // 更新节点 u 的出边起始位置
        tot++; // 增加边数
    }

    private void traverseFrom(int a) {
        System.out.println("Traversing from node " + a);
        for (int i = head[a]; i != -1; i = next[i]) {
            int v = edge[i];
            int w = weight[i];
            System.out.println(a + " -> " + v + " weight: " + w);
        }
    }

    public static void main(String[] args) {
        LinkedForwardStar lfs = new LinkedForwardStar();
        lfs.add(1, 2, 1);
        lfs.add(2, 3, 2);
        lfs.add(1, 3, 1);
        lfs.add(2, 4, 2);
        // 遍历从各个节点出去的边
        for (int i = 1; i < 5; i++) {
            lfs.traverseFrom(i);
        }
    }
}

Appendix

图论 - 存图方式 - 三叶

非链式前向星的建图方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // 图中共有 numCourses 个节点
    List<Integer>[] graph = new LinkedList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new LinkedList<>();
    }
    for (int[] edge : prerequisites) {
        int from = edge[1];
        int to = edge[0];
        graph[from].add(to);
    }
    return graph;
}