首先学习三种存图方式
约定 n 为点数，m 为边数
- 邻接表
与数组存储单链表的实现一致（头插法）
「稀疏图」：m≈n
int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];//idx表示当前边的下标int idx;//a节点指向b节点，权重为cvoid add(int a, int b, int c) {e[idx] = b; //e数组存储当前边指向的节点w[idx] = c; //w数组存储当前节点的权重ne[idx] = he[a]; //ne数组用于找到下一条边he[a] = idx; //he数组存储当前边所对应边的集合（链表）的头节点idx++;}//遍历所有由 a 点发出的边for (int i = he[a]; i != -1; i = ne[i]) {int b = e[i], c = w[i];}
- 邻接矩阵
二维矩阵来进行存图
「稠密图」: 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;}
- 类
若有收获，就点个赞吧
0 人点赞
