图的存储

n表示节点
m表示边数

邻接表

链式前向星存图

用于存储稀疏图，即 n ~ m

int[] h, e, w, ne;
int idx;
h = new int[n + 1];
Arrays.fill(h, -1);
e = new int[m];
w = new int[m];
ne = new int[m];
idx = 0;
//插入一条从a指向b的边，权重为c
void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

邻接矩阵

用于存储稠密图，即 n ~ m``2

int[][] g;
g[a][b] = w;