4. DAG的表示方法

聊完了DAG是什么、怎么判断环，接下来得面对一个实际问题：代码里怎么存DAG？

你想想看，一个图可能有几千个节点、几万条边。选错数据结构，轻则写代码费劲，重则性能崩盘。我个人习惯是，先搞清楚场景再选方案——没有银弹，只有最合适的。

4.1 三种表示法概览

先给个全景图。DAG的存储方案，主流就这三种：

表示法	核心思路	空间复杂度	查边速度	适用场景
邻接矩阵	二维数组，行列对应节点	O(V²)	O(1)	稠密图、小规模图
邻接表	每个节点挂一个链表/数组	O(V+E)	O(度)	稀疏图、工程实战
边列表	三元组 (u, v, w) 平铺	O(E)	O(E)	算法中间态、序列化

嗯，这里要注意：V是节点数，E是边数。大部分真实DAG都是稀疏图——E远小于V²。所以邻接表是工程里的常胜将军。

4.2 邻接矩阵：简单粗暴，但吃内存

邻接矩阵说白了就是一个 V × V 的二维数组。第 i 行第 j 列存 1 表示 i→j 有边，存 0 表示没有。

// 用二维数组表示DAG
// 节点: A=0, B=1, C=2, D=3
// 边: A→B, A→C, B→D, C→D

int[][] matrix = {
    {0, 1, 1, 0},  // A
    {0, 0, 0, 1},  // B
    {0, 0, 0, 1},  // C
    {0, 0, 0, 0}   // D
};

// 查A→C是否有边：matrix[0][2] == 1 → 有
// 查C→A是否有边：matrix[2][0] == 0 → 无

4.3 邻接表：工程首选

邻接表的思路是：每个节点维护一个列表，只存它指向的邻居。这样有多少条边，就存多少条记录。

// 用邻接表表示DAG
// 节点: A, B, C, D
// 边: A→B, A→C, B→D, C→D

Map<String, List<String>> graph = new HashMap<>();

graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("D"));
graph.put("C", Arrays.asList("D"));
graph.put("D", new ArrayList<>());  // 叶子节点也要占位

// 查A的邻居：graph.get("A") → [B, C]
// 查D的邻居：graph.get("D") → []

实际工程里，我更推荐用 邻接表 + 入度数组 的组合。入度就是指向某个节点的边数。这个组合在拓扑排序时特别好用。

// 邻接表 + 入度数组
// 节点编号: A=0, B=1, C=2, D=3

List<Integer>[] adj = new List[4];
int[] inDegree = new int[4];

// 初始化
for (int i = 0; i < 4; i++) adj[i] = new ArrayList<>();

// 加边 A→B
adj[0].add(1);
inDegree[1]++;  // B的入度+1

// 加边 A→C
adj[0].add(2);
inDegree[2]++;  // C的入度+1

// 加边 B→D
adj[1].add(3);
inDegree[3]++;  // D的入度+1

// 加边 C→D
adj[2].add(3);
inDegree[3]++;  // D的入度再+1

// 结果：inDegree = [0, 1, 1, 2]
// 入度为0的节点就是起点

4.4 边列表：轻量级选手

边列表最简单——就是把所有边平铺出来。每条边存成 (起点, 终点, 权重) 的三元组。

// 边列表表示DAG
// 边: A→B, A→C, B→D, C→D

class Edge {
    int from, to, weight;
    Edge(int f, int t, int w) { from = f; to = t; weight = w; }
}

List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 1));  // A→B
edges.add(new Edge(0, 2, 1));  // A→C
edges.add(new Edge(1, 3, 1));  // B→D
edges.add(new Edge(2, 3, 1));  // C→D

// 查A的所有出边：遍历edges，找from==0的
// 查D的所有入边：遍历edges，找to==3的

4.5 三种方案的对比与选择

我整理了一张对比表，方便你快速决策：

维度	邻接矩阵	邻接表	边列表
空间占用	高 (V²)	低 (V+E)	最低 (E)
查u→v	O(1) ⚡	O(度(u))	O(E) 🐢
遍历u的出边	O(V)	O(度(u)) ⚡	O(E) 🐢
加边/删边	O(1)	O(1) (链表头插)	O(1) (尾部追加)
拓扑排序	O(V²)	O(V+E) ⚡	O(V·E) 🐢
代码复杂度	低	中	最低

说白了，选型就一句话：工程实战无脑邻接表，稠密小图用矩阵，序列化/排序用边列表。

4.6 一张图看懂三种表示法

下面这张SVG图，把同一个DAG用三种方式画出来。你可以直观感受它们的差异。

4.7 实战建议：我一般这么选

最后分享一点个人经验。不同阶段、不同场景，我的选择策略不太一样：

• 写算法题/做原型：用邻接矩阵。代码短，不容易写错。反正数据量小，无所谓性能。
• 做工程系统：用邻接表 + 入度数组。这是最稳的组合，拓扑排序、路径查找、环检测都能高效搞定。
• 存文件/传网络：用边列表。JSON格式就是 [{"from":"A","to":"B"}, ...]，清晰又好解析。
• 做图数据库/大规模计算：用邻接表，但底层用压缩稀疏行（CSR）格式。这个后面讲到性能优化时会细聊。