如何修改拓扑排序（Topological Sort）以处理并发先修课程？

核心思路调整 #

把原来的严格先修依赖（A必须在B之前修读），转化为非后修约束（A不能在B之后修读）。这样既保留了"A先于B"的合法情况，也允许"A与B同时修读"的场景。

具体实现步骤 #

1. 重构依赖图的边定义 #

• 原逻辑中A → B表示：必须先修完A才能修B（严格先后顺序）
• 修改后A → B表示：A的修读时间不能晚于B的修读时间（允许A先于B，或二者同时修）

2. 松弛拓扑排序的节点选择逻辑 #

基于标准Kahn算法做调整，核心改动是允许同一学期批量选满足约束的课程：

• 每次迭代时，不再只选单个入度为0的节点，而是收集**所有入度为0、且所有前置约束已满足（前置课已修或可同期修）**的课程，将它们归入同一学期
• 处理完当前学期的课程后，更新剩余节点的入度：对每个后续课程X，若其所有前置课要么已安排在之前学期，要么和X在当前学期，则将X的入度减1

3. 示例落地（计算机导论+数据结构） #

假设数据结构（DS）的约束是「计算机导论（CS101）不能晚于DS修读」：

• 构建依赖边CS101 → DS
• 拓扑排序第一轮，入度为0的节点是CS101，此时可以选择把CS101和DS同时加入第一学期（满足"CS101不晚于DS"的约束）；也可以只安排CS101，第二学期再安排DS——两种情况都合法
• 若要生成紧凑课程表，优先把所有满足约束的课程塞进同一学期即可

4. 代码层面的关键改动（基于Kahn算法） #

def relaxed_topological_sort(graph):
    # 初始化入度表
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    semesters = []
    while in_degree:
        # 收集当前学期可安排的所有课程
        current_semester = [node for node in in_degree if in_degree[node] == 0]
        if not current_semester:
            raise ValueError("课程存在循环依赖，无法生成合法课表")
        
        semesters.append(current_semester)
        # 更新后续课程的入度状态
        for node in current_semester:
            del in_degree[node]
            for neighbor in graph.get(node, []):
                if neighbor not in in_degree:
                    continue
                # 检查该后续课程的所有前置是否都已安排（含当前学期）
                all_prereq_met = True
                for prereq in graph:
                    if neighbor in graph[prereq]:
                        if prereq not in [n for sem in semesters for n in sem] and prereq not in current_semester:
                            all_prereq_met = False
                            break
                if all_prereq_met:
                    in_degree[neighbor] -= 1
    return semesters

额外优化方向 #

• 加入学分上限、单学期课程数量限制，在选择当前学期课程时做过滤，避免课程过载
• 支持两种模式切换：「优先紧凑安排」（尽可能把满足约束的课塞同一学期）和「优先分散安排」（尽量拆分到不同学期）

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