如何修改DFS结合图论、拓扑排序校验课程先修及同修要求

我们首先将大学课程依赖体系抽象为有向无环图（DAG）：每个节点对应一门课程，有向边的类型分为两种，A→B标记为先修边代表A是B的必选先修，无向边A-B标记为同修边代表A和B必须同一学期修。由于课程依赖不能存在循环，首先会通过拓扑排序校验整个图的合法性，存在环的依赖体系直接判定为无效。

• 先修课：必须在目标课程X之前修完的课程，对应DAG中所有可通过先修边到达X的前驱节点
• 同修课：必须和目标课程X同一学期修读的课程，不存在前置顺序要求，仅存在同期修读约束

原版DFS仅做节点访问标记，我们针对两类依赖的查询需求做如下修改：

前置准备 #

新增三类存储结构：

• 反向先修邻接表：将所有先修边的方向反转，用于从X出发逆向查找所有前驱节点
• 同修邻接表：存储所有无向同修边，用于查找X的关联同修课程
• 两个结果集合：prereq_set存储先修课结果，coreq_set存储同修课结果

先修课查询DFS逻辑 #

1. 清空访问标记与prereq_set，从目标课程X节点出发，在反向先修邻接表上启动DFS
2. 每访问到一个未标记的节点，直接加入prereq_set，同时标记为已访问
3. 递归遍历当前节点的所有反向邻接节点，重复步骤2
4. 若遍历过程中遇到已在prereq_set中的节点，说明存在循环先修依赖，抛出配置错误

该逻辑本质是找到X在原DAG中的所有可达前驱，和拓扑排序的依赖校验逻辑完全一致，查询到的先修课顺序满足拓扑序要求。

同修课查询DFS逻辑 #

1. 清空访问标记，保留已查询到的prereq_set结果，从X出发在同修邻接表上启动DFS
2. 每访问到一个未标记的节点，首先校验是否存在于prereq_set中，若存在说明依赖冲突（同一课程不能既是先修又是同修），抛出配置错误
3. 校验通过后将该节点加入coreq_set，标记为已访问
4. 递归遍历当前节点的所有同修邻接节点，重复步骤2-3

得到两个结果集合后，可直接校验排课是否符合要求：

• 所有prereq_set内的课程，排课学期编号必须小于X的排课学期编号
• 所有coreq_set内的课程，排课学期编号必须等于X的排课学期编号
• 两个结果集合的交集必须为空，否则判定为课程依赖配置错误

from collections import defaultdict

# 原始依赖配置存储
prereq_adj = defaultdict(list)  # prereq_adj[A] = [B] 代表A是B的先修课
coreq_adj = defaultdict(list)   # coreq_adj[A] = [B] 代表A和B是同修课
reversed_prereq_adj = defaultdict(list) # 反向先修邻接表

visited = set()
prereq_set = set()
coreq_set = set()

# 查询目标课程X的先修课
def dfs_find_prereq(node: str):
    visited.add(node)
    for prev_course in reversed_prereq_adj[node]:
        if prev_course in prereq_set:
            raise Exception(f"存在循环先修依赖：{prev_course} <-> {node}")
        if prev_course not in visited:
            prereq_set.add(prev_course)
            dfs_find_prereq(prev_course)

# 查询目标课程X的同修课
def dfs_find_coreq(node: str):
    visited.add(node)
    for co_course in coreq_adj[node]:
        if co_course in prereq_set:
            raise Exception(f"依赖冲突：{co_course} 不能同时是 {node} 的先修课与同修课")
        if co_course not in visited:
            coreq_set.add(co_course)
            dfs_find_coreq(co_course)

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