约定 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²时,可定义为「稠密图」。

// 邻接矩阵数组: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 时,可定义为「稀疏图」。

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伸出的边) 时,可使用如下方式:

// 从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) 时,才会考虑使用。

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

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

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

List<Edge> es = new ArrayList<>();
...
for (Edge e : es) {
...
}

4.HashMap

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

key为出发点,value为该出发点对应的终点列表(一个出发点可能对应多个终点)

// 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]);
}