如何在课程依赖有向图中找到瓶颈课程？

你的问题本质是在**有向无环图（DAG）**中寻找与关键路径相关的节点，瓶颈课程的核心特征是：它所在的前置路径是目标课程所有前置路径中最长的，直接决定了目标课程的最早可修读时间。

适用算法：基于拓扑排序的关键路径算法 #

执行步骤 #

1. 验证图的合法性
   • 先通过拓扑排序确认课程依赖图是无环的（DAG），有环的依赖无法完成修读，需先处理环的问题。
2. 计算每个课程的最早开始时间（EST）
   • 定义：EST代表修读该课程前必须完成的最长前置路径的步骤数（默认每门课程修读时间为1，因为支持并行修读）。
   • 计算逻辑：
     • 初始化所有入度为0的课程（无先修要求）的EST为1。
     • 按照拓扑排序的顺序遍历每个课程，对其所有后继课程，更新后继的EST为 max(当前后继EST, 当前课程EST + 1)。
3. 定位目标课程的瓶颈
   • 找到目标课程的所有直接先修课程（即直接指向它的节点），其中EST值最大的那个就是瓶颈课程——因为它的前置路径最长，是最后完成的先修课，会卡住目标课程的修读时间。
   • 如果要找全局瓶颈（影响整个修读流程总时长的课程），则是关键路径上的所有节点：关键路径是从入度0节点到出度0节点的最长路径，路径上的每个节点延迟都会直接拖慢整体流程。

示例验证 #

针对你给出的先修关系[2,1],[3,2],[6,3],[5,4],[6,5]（注：[2,1]表示修读课程2前需完成课程1，对应有向边1→2）：

• 拓扑排序可行顺序：1,4,2,5,3,6
• 各课程EST计算：
  • EST(1)=1，EST(4)=1
  • EST(2)=EST(1)+1=2，EST(5)=EST(4)+1=2
  • EST(3)=EST(2)+1=3
  • EST(6)=max(EST(3)+1, EST(5)+1)=4
• 课程6的直接先修是3和5，EST(3)=3 > EST(5)=2，因此3是课程6的瓶颈，与示例一致。

实现提示 #

• 用邻接表存储课程间的依赖关系，同时维护每个节点的入度表，方便拓扑排序的执行。
• 拓扑排序可通过队列实现：初始将所有入度为0的节点入队，每次取出节点后更新其后继的入度，入度变为0的节点入队。
• 计算EST时，只需在拓扑排序的遍历过程中同步更新即可，无需额外遍历。

内容的提问来源于stack exchange，提问作者jmtt