📝 写在前面

在项目规划、课程安排、编译依赖等场景中，经常需要处理任务之间的先后顺序。拓扑排序可以帮我们将有向无环图（DAG）中的顶点排成一个线性序列，使得对每一条有向边 (u→v)，u 都出现在 v 之前。而关键路径则是项目管理中的核心问题——找出影响整个项目工期的关键任务，即最长路径。

阅读指南：每个部分包含👇

• 一句话记住：核心思想速记

• 核心思想：原理详解

• 流程图：算法流程图片

• 代码实现：带详细注释

• LeetCode实战：典型例题+解题代码

---

一、拓扑排序

🎯 一句话记住

把依赖关系排成先后顺序，没有环才能排。

🤔 核心思想

拓扑排序是针对有向无环图（DAG）的一种排序算法，它将所有顶点排成一个线性序列，使得对于每一条有向边 (u→v)，顶点 u 都出现在顶点 v 之前。拓扑排序的常见实现方式有两种：

1. Kahn算法（基于入度）：不断删除入度为 0 的顶点，并更新其邻接点的入度，直到所有顶点都被删除。

2. DFS 算法：对图进行深度优先搜索，在回溯时将顶点加入结果栈，最后逆序输出。

算法步骤（Kahn算法）：

• 计算每个顶点的入度

• 将所有入度为 0 的顶点入队

• 当队列非空时：

  • 取出队首顶点 u，将其加入结果序列

  • 对于 u 的每个邻接点 v，将 v 的入度减 1；若 v 的入度变为 0，则入队

• 如果结果序列中的顶点数小于总顶点数，说明图中有环，无法拓扑排序

📊 流程图

💻 代码实现

1. Kahn算法（BFS）

/**
 * Kahn算法求拓扑排序
 * @param {number} n 顶点数（0~n-1）
 * @param {number[][]} edges 有向边集 [u, v]
 * @returns {number[]} 拓扑序列，若存在环则返回空数组
 */
function topologicalSortKahn(n, edges) {
    // 构建邻接表
    const graph = Array.from({ length: n }, () => []);
    const inDegree = new Array(n).fill(0);
    
    for (const [u, v] of edges) {
        graph[u].push(v);
        inDegree[v]++;
    }
    
    const queue = [];
    for (let i = 0; i < n; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }
    
    const result = [];
    while (queue.length) {
        const u = queue.shift();
        result.push(u);
        
        for (const v of graph[u]) {
            inDegree[v]--;
            if (inDegree[v] === 0) {
                queue.push(v);
            }
        }
    }
    
    return result.length === n ? result : [];
}

2. DFS 算法（基于栈）

/**
 * DFS法求拓扑排序
 * @param {number} n 顶点数
 * @param {number[][]} edges 有向边集
 * @returns {number[]} 拓扑序列，若存在环则返回空数组
 */
function topologicalSortDFS(n, edges) {
    const graph = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) graph[u].push(v);
    
    const visited = new Array(n).fill(0); // 0=未访问, 1=访问中, 2=已访问
    const stack = [];
    let hasCycle = false;
    
    function dfs(u) {
        if (visited[u] === 1) { hasCycle = true; return; }
        if (visited[u] === 2) return;
        visited[u] = 1;
        for (const v of graph[u]) {
            dfs(v);
            if (hasCycle) return;
        }
        visited[u] = 2;
        stack.push(u);
    }
    
    for (let i = 0; i < n; i++) {
        if (visited[i] === 0) dfs(i);
        if (hasCycle) return [];
    }
    
    return stack.reverse(); // 逆序得到拓扑序列
}

🏆 LeetCode实战：课程表

题目：LeetCode 207. 课程表

题目描述：你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses-1。在选修某些课程之前需要一些先修课程。给定一个数组 prerequisites，其中 prerequisites[i] = [ai, bi] 表示如果要学习课程 ai 则必须先学习课程 bi。请你判断是否可能完成所有课程的学习（即是否存在拓扑排序）。

解题代码（Kahn算法）：

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    const graph = Array.from({ length: numCourses }, () => []);
    const inDegree = new Array(numCourses).fill(0);
    
    for (const [a, b] of prerequisites) {
        graph[b].push(a);
        inDegree[a]++;
    }
    
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }
    
    let count = 0;
    while (queue.length) {
        const u = queue.shift();
        count++;
        for (const v of graph[u]) {
            inDegree[v]--;
            if (inDegree[v] === 0) queue.push(v);
        }
    }
    
    return count === numCourses;
};

时间复杂度：O(V+E)
空间复杂度：O(V+E)

---

二、关键路径

🎯 一句话记住

项目管理中，从开始到结束的最长路径，决定整个项目的工期。

🤔 核心思想

关键路径是指在有向无环图中，从起点到终点的所有路径中，路径长度（权值和）最大的那条路径。它反映了整个项目的最短完成时间，并且关键路径上的任何活动延误都会导致整个项目延期。

关键概念：

• 事件的最早发生时间 ve[v]：从起点到达顶点 v 的最长路径长度

• 事件的最迟发生时间 vl[v]：在不影响整个项目工期的前提下，事件 v 最晚可以发生的时间

• 活动的最早开始时间：边的起点事件的最早发生时间

• 活动的最迟开始时间：边的终点事件的最迟发生时间减去边的权值

• 关键活动：最早开始时间等于最迟开始时间的活动

算法步骤：

1. 对图进行拓扑排序，得到拓扑序列

2. 按拓扑顺序计算每个顶点的最早发生时间 ve（动态规划：ve[v] = max(ve[u] + w(u,v))）

3. 按逆拓扑顺序计算每个顶点的最迟发生时间 vl（vl[u] = min(vl[v] - w(u,v))）

4. 计算每条边的关键活动，最早开始时间 = 最迟开始时间的边即为关键路径

📊 流程图

💻 代码实现

/**
 * 计算关键路径（求有向无环图的最长路径）
 * @param {number} n 顶点数
 * @param {number[][]} edges 边集 [u, v, w]（活动持续时间）
 * @returns {number} 关键路径长度（项目最短工期）
 */
function criticalPath(n, edges) {
    // 构建邻接表
    const graph = Array.from({ length: n }, () => []);
    const inDegree = new Array(n).fill(0);
    for (const [u, v, w] of edges) {
        graph[u].push({ to: v, weight: w });
        inDegree[v]++;
    }
    
    // 1. 拓扑排序（Kahn）
    const queue = [];
    for (let i = 0; i < n; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }
    const topo = [];
    while (queue.length) {
        const u = queue.shift();
        topo.push(u);
        for (const { to: v } of graph[u]) {
            inDegree[v]--;
            if (inDegree[v] === 0) queue.push(v);
        }
    }
    if (topo.length !== n) return -1; // 存在环，无法计算
    
    // 2. 计算最早发生时间 ve
    const ve = new Array(n).fill(0);
    for (const u of topo) {
        for (const { to: v, weight } of graph[u]) {
            if (ve[u] + weight > ve[v]) {
                ve[v] = ve[u] + weight;
            }
        }
    }
    const projectTime = Math.max(...ve); // 项目总工期
    
    // 3. 计算最迟发生时间 vl
    const vl = new Array(n).fill(projectTime);
    for (let i = topo.length - 1; i >= 0; i--) {
        const u = topo[i];
        for (const { to: v, weight } of graph[u]) {
            if (vl[v] - weight < vl[u]) {
                vl[u] = vl[v] - weight;
            }
        }
    }
    
    // 4. 输出关键路径（可选）
    const criticalEdges = [];
    for (const [u, v, w] of edges) {
        if (ve[u] === vl[v] - w) {
            criticalEdges.push([u, v, w]);
        }
    }
    
    return projectTime;
}

🏆 LeetCode实战：并行课程 III

题目：LeetCode 2050. 并行课程 III

题目描述：给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n。同时给你一个二维整数数组 relations ，其中 relations[j] = [prevCourse_j, nextCourse_j] 表示课程 prevCourse_j 必须在课程 nextCourse_j 之前 完成。同时给你一个下标从 0 开始的整数数组 time ，其中 time[i] 表示完成第 i+1 门课程需要花费的月份数。请你计算出完成所有课程所需要的最少月份数。

思路分析：
这实际上是一个有向无环图（DAG）上的最长路径问题。每个课程的完成时间取决于所有先修课程的完成时间中的最大值（因为必须先修完所有前置课程才能开始当前课程）。我们可以用动态规划，按照拓扑顺序计算每个课程的最早完成时间：dp[v] = max(dp[u]) + time[v]，其中 u 是 v 的前置课程。最终答案就是所有 dp 中的最大值。

解题代码：

/**
 * @param {number} n
 * @param {number[][]} relations
 * @param {number[]} time
 * @return {number}
 */
var minimumTime = function(n, relations, time) {
    const graph = Array.from({ length: n }, () => []);
    const inDegree = new Array(n).fill(0);
    
    for (const [prev, next] of relations) {
        graph[prev - 1].push(next - 1);
        inDegree[next - 1]++;
    }
    
    const queue = [];
    const dp = new Array(n).fill(0);
    
    // 初始化入度为0的课程，其完成时间就是time[i]
    for (let i = 0; i < n; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
            dp[i] = time[i];
        }
    }
    
    while (queue.length) {
        const u = queue.shift();
        for (const v of graph[u]) {
            // 完成课程v的时间 = max(所有前置课程完成时间) + time[v]
            dp[v] = Math.max(dp[v], dp[u] + time[v]);
            inDegree[v]--;
            if (inDegree[v] === 0) {
                queue.push(v);
            }
        }
    }
    
    return Math.max(...dp);
};

时间复杂度：O(V+E)
空间复杂度：O(V+E)

---

三、拓扑排序与关键路径对比

特性	拓扑排序	关键路径
适用图	有向无环图（DAG）	有向无环图（DAG）
目标	生成一个线性序列	找出最长路径及其关键活动
核心算法	Kahn（BFS）或 DFS	拓扑排序 + 动态规划
时间复杂度	O(V+E)	O(V+E)
应用场景	课程安排、编译依赖	项目调度、工期估算

---

📌 面试常见问题

1. 拓扑排序的两种实现方法有什么区别？

   • Kahn算法（BFS）使用队列处理入度为0的顶点，直观且易于检测环；DFS算法使用栈和颜色标记，递归实现简洁，但需要注意栈溢出。

2. 如何检测图中是否存在环？

   • Kahn算法：如果最终输出的顶点数少于总顶点数，则存在环。

   • DFS：如果递归过程中遇到状态为“访问中”的顶点，则存在环。

3. 关键路径和最短路径有什么联系？

   • 关键路径是图中的最长路径，通常可以通过将边权取负转化为最短路径问题（但需要无环）。

4. 关键路径上的活动有什么特点？

   • 关键活动的松弛时间为0，即最早开始时间等于最迟开始时间，任何延误都会导致项目延期。

---

🎯 下期预告

下一期我们将进入图论算法（五）：网络流——最大流、最小割、二分图匹配，用图论解决资源分配和匹配问题！

如果你觉得这篇文章对你有帮助，欢迎点赞、收藏、转发！