图的存储

• 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]; }

（全文完）