图的存储

• OI Wiki: https://oi-wiki.org/graph/save/

图的存储

// 邻接数组
// adj[u][v] = w；初始化一般 w 设为 INF（无穷大）；当 u==v 时，w 为 0；当为无权图时，可以退化成 boolean[][] adj;
int[][] adj;
// 获取下一跳
for (int v = 0; v < n; v++) {
    if (u != v && adj[u][v] != INF){}
}

// 集合类（类似邻接表）
// adj.get(u) = {v, w}；当为无权图时，可以退化成 Map<Integer, List<Integer>>;
Map<Integer, List<int[]>> adj;
// 获取下一跳
for (int[] tuple : graph.getOrDefault(u, new ArrayList<>())) {}

// 链式前向星
int[] he = new int[N], ne = new int[M], ed = new int[M], we = new int[M];
int idx = 0;
void add(int u, int v, int w) {
    ed[idx] = v;
    ne[idx] = he[u];
    he[u] = idx;
    we[idx] = w;
    idx++;
}
// 获取下一跳
for (int i = he[u]; i != -1; i = ne[i]) {
    int v = ed[i];
    int w = we[i];
}

（全文完）