在拓扑排序（如课程表问题）中，邻接表必须按“依赖源 → 依赖目标”方向构建（即 prerequisite → course），才能支持高效正向遍历；若反向构建（course → prerequisite），则每次查找后续节点需全表扫描，时间复杂度从 o(1) 退化为 o(n)。
拓扑排序的本质是模拟依赖流的正向传播过程：从无前置依赖的节点（入度为 0）出发，逐步访问其所有直接后继，并更新它们的依赖状态。因此，邻接表的设计必须服务于这一“源 → 目标”的遍历逻辑。
✅ 正确建图：prerequisite → course（推荐且标准）
这表示“完成 prerequisite 后，可解锁 course”，即图中存在一条有向边 prerequisite → course。该设计使 BFS/DFS 能自然推进：
- 入度为 0 的节点（如课程 0）作为起点；
- 查找其邻接节点（adjMap.get(0) 返回 [1, 2]），即“0 能开启哪些课？”——答案直接可得；
- 每次处理一个节点，仅需常数时间获取全部后继。
// 正确：prerequisite → course
private Map> createAdjacencyList(int[][] prerequisites) {
Map> adjMap = new HashMap<>();
for (int[] edge : prerequisites) {
int course = edge[0]; // 目标课程（被依赖者）
int prereq = edge[1]; // 前置课程（依赖源）
adjMap.computeIfAbsent(prereq, k -> new ArrayList<>()).add(course);
}
return adjMap;
}
❌ 错误建图：course → prerequisite
若定义为 course → [prereq1, prereq2]，语义上虽符合“某课依赖哪些先修课”，但与拓扑排序的执行流相悖：
- 起点（入度为 0 的课）仍可识别；
- 但要找出“哪些课依赖当前课？”，需遍历整个邻接表或额外维护反向索引，每次查找后继代价为 O(V+E)，严重拖慢性能。
? 关键原则：邻接表的键（key）应为遍历的“出发点”，值（value）为“可达的目标”。拓扑排序从无依赖者出发、走向被依赖者，故边方向必须是 依赖源 → 依赖目标。
补充说明：入度数组的构建逻辑
入度统计必须与邻接表方向严格一致：
- 每条边 prereq → course 意味着 course 的入度 +1；
- prereq 自身入度不受此边影响（除非它在其他边中作为目标出现）。
Map indegree = new HashMap<>();
// 初始化所有出现过的课程（含前置和目标）
for (int[] e : prerequisites) {
indegree.put(e[0], 0); // course
indegree.put(e[1], 0); // prereq
}
// 统计每门课作为 target 出现的次数
for (int[] e : prerequisites) {
indegree.merge(e[0], 1, Integer::sum); // e[0] 是被依赖者，入度+1
}
总结：三步建图心法
-
明确语义方向：问自己“算法从哪开始？往哪走？”——拓扑排序是“从因到果”，边必须是 原因 → 结果（即 prereq → course）；
-
邻接表服务遍历：adjMap.get(u) 应直接返回所有 v，满足 u → v，且 v 是下一步待处理节点；
-
入度与边对齐：每条 u → v 边，只增加 v 的入度，不改变
u 的入度。
遵循此逻辑，不仅适用于课程表问题，也普适于所有基于依赖关系的 DAG 拓扑排序场景（如任务调度、编译依赖解析、包安装顺序等）。
