约定 n 为点数， m为边数，times = [[2,1,1],[2,3,1],[3,4,1]] 表示3条边

2->1 权重为1

2->3 权重为1

3->4 权重为1

1.邻接矩阵

这是一种使用二维矩阵来进行存图的方式。

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

1
2
3
4
5
6
7
// 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
int[][] w = new int[N][N];

// 加边操作
void add(int a, int b, int c) {
    w[a][b] = c;
}

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;    // 边idx指向节点b
    ne[idx] = he[a];    // 头插法在上一轮的a射出的边的头结点上插入idx
    he[a] = idx;    // 更新a射出的边的头结点为边idx
    w[idx] = c;    // 边idx的权重为c
    idx++;        // 边索引+1
}

首先 idx 是用来对边进行编号的：

1.he 数组：存储是某个节点所对应的边的集合（链表）的头结点；

如下图所示：he[u]=边4

注意：仅仅是存储头结点，之后就可以根据ne数组进行查找！

p20

2.e 数组：某一条边指向的节点：e[边4]=v4

3.ne 数组：由于是以链表的形式进行存边，该数组用于找到下一条边

ne[边4]=边3；构建链表的过程是头插法：null<-边1<-边2…

4.w 数组：用于记录某条边的权重为多少。

编码的边是用idx作为索引来进行标记的，也就是说每一个idx对应一条边

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

1
2
3
4
// 从a射出的边的头结点出发一路遍历至-1(null)
for (int i = he[a]; i != -1; i = ne[i]) {
    int b = e[i], c = w[i]; // 存在由 a 指向 b 的边，权重为 c
}

3.类

这是一种最简单，但是相比上述两种存图方式，使用得较少的存图方式。

只有当我们需要确保某个操作复杂度严格为O(m) 时，才会考虑使用。

具体的，我们建立一个类来记录有向边信息：

1
2
3
4
5
6
7
class Edge {
    // 代表从 a 到 b 有一条权重为 c 的边
    int a, b, c;
    Edge(int _a, int _b, int _c) {
        a = _a; b = _b; c = _c;
    }
}

通常我们会使用 List 存起所有的边对象，并在需要遍历所有边的时候，进行遍历：

1
2
3
4
5
List<Edge> es = new ArrayList<>();
...
for (Edge e : es) {
    ...
}

4.HashMap

注意：如果节点索引集中可以用List数组代替HashMap，具体参考List数组创建与初始化方法

key为出发点，value为该出发点对应的终点列表（一个出发点可能对应多个终点）

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
// HashMap存图(适用于离散节点)
HashMap<Integer, List<Integer>> map = new HashMap<>();
for (int[] edge : edges) {
    List<Integer> list1 = map.getOrDefault(edge[0], new ArrayList<>());
    list1.add(edge[1]);
    map.put(edge[0], list1);
    // 若为无向图
    List<Integer> list2 = map.getOrDefault(edge[1], new ArrayList<>());
    list2.add(edge[0]);
    map.put(edge[1], list2);
}

// 带权图
HashMap<Integer, List<int[]]>> map = new HashMap<>();
for (int[] edge : edges) {
    List<int[]> list1 = map.getOrDefault(edge[0], new ArrayList<>());
    list1.add(new int[] {edge[1], edge[2]});
    map.put(edge[0], list1);
    // 若为带权无向图
    List<Integer> list2 = map.getOrDefault(edge[1], new ArrayList<>());
    list2.add(new int[] {edge[0], edge[2]});
    map.put(edge[1], list2);
}


// 邻接表存图(适用于集中节点)
List<Integer>[] list = new List[n];
// 注意这里不能Arrays.fill()否则是同一个对象
for (int i = 0; i < n; i++) list[i] = new ArrayList<>();
for (int[] e : edges) {
    // e[0] -> e[1]
    list[e[0]].add(e[1]);
    // 若为无向图
    list[e[1]].add(e[0]);
}