51工具盒子约定 n 为点数， m为边数，times = [[2,1,1],[2,3,1],[3,4,1]] 表示3条边
2->1 权重为1
2->3 权重为1
3->4 权重为1
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.邻接表(链式前向星存图) {#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数组进行查找！
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.类 {#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 {#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]); } |
