如何正确构建有向图的邻接表：拓扑排序中边方向的核心逻辑

碧海醫心

发布时间：2026-01-11 10:04:45

481人浏览过

来源于php中文网

原创

如何正确构建有向图的邻接表：拓扑排序中边方向的核心逻辑

在拓扑排序（如课程表问题）中，邻接表必须按“依赖源 → 依赖目标”方向构建（即 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]，语义上虽符合“某课依赖哪些先修课”，但与拓扑排序的执行流相悖：

ClippingMagic

魔术般地去除图片背景

下载

起点（入度为 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
}