Python作业第3、4题求助：拓扑排序代码致程序死循环

问题说明 #

我在做一份Python作业，已经搞定第1、2题，现在卡在前两道：

• 第3题：自己写的拓扑排序代码跑grader.py时直接死循环了
• 第4题：完全没头绪，不知道从哪下手

作业核心文件是network.py，运行grader.py能看4道题的得分情况。

我写的第3题代码： #

for i in self.node:
    self.node[i].order = []
node_list= list()
    for i in self.node:
        if len(self.node[i].reverseStar) == 0:
            node_list.append(i)
            break
if len(node_list)== 0:
    raise BadNetworkOperationException()
while (len(node_list)!=self.numNodes):
    for i in [x for x in self.node if x not in node_list]:
        incoming_nodes = [int(j[1]) for j in self.node[i].reverseStar if j not in node_list]
        if (len(incoming_nodes)== 0):
            node_list.append(i)
            break
for k in range(len(node_list)):
    self.node[node_list[k]].order = k+1
return self.node[i].order

第3题死循环问题修复 #

你的代码有几个明显问题，直接导致了死循环：

1. 初始节点只找一个：找到第一个入度为0的节点就break，如果图里有多个入度为0的节点，剩下的根本没机会被加入，后续循环自然推进不了。
2. 入度判断逻辑搞反了：incoming_nodes是统计不在node_list里的前驱节点，你判断这个列表为空就加入节点——这逻辑错了，应该是所有前驱都在node_list里（也就是没有未处理的前驱）才能加。
3. 无环检查缺失：如果图里有环，或者某次循环找不到符合条件的节点，while循环会一直转，永远到不了len(node_list) == self.numNodes的终止条件。
4. 返回值乱了：最后返回self.node[i].order，但i是最后一次循环的变量，根本不是你要返回的目标节点。

下面是修正后的代码（用Kahn算法，这是拓扑排序的标准实现）：

# 初始化所有节点的order为0
for node_id in self.node:
    self.node[node_id].order = 0

# 先统计每个节点的入度
in_degree = {}
for node_id in self.node:
    in_degree[node_id] = len(self.node[node_id].reverseStar)

# 把所有入度为0的节点都加入队列
node_list = [node_id for node_id in self.node if in_degree[node_id] == 0]

if not node_list:
    raise BadNetworkOperationException()

order_count = 1
while node_list:
    # 取出队列里的第一个节点（用队列保证拓扑顺序）
    current_node = node_list.pop(0)
    self.node[current_node].order = order_count
    order_count += 1

    # 遍历当前节点的所有后继，把它们的入度减1
    for edge in self.node[current_node].star:  # 假设star是当前节点的出边列表，格式和reverseStar对应
        neighbor_id = edge[1]  # 取边指向的后继节点ID
        in_degree[neighbor_id] -= 1
        # 如果后继节点入度变成0，就加入队列
        if in_degree[neighbor_id] == 0:
            node_list.append(neighbor_id)

# 检查是否所有节点都被处理了（如果没处理完，说明图里有环）
if order_count - 1 != self.numNodes:
    raise BadNetworkOperationException()

# 这里可以根据需求返回，比如返回特定节点的order，或者所有节点的order映射
return self.node[current_node].order

核心修正点： #

• 用队列管理入度为0的节点，一次处理所有符合条件的节点，不是只找一个就停
• 维护入度字典，处理完节点就更新后继的入度，逻辑更清晰
• 最后加了环检查，避免因为有环导致死循环

第4题思路提示 #

结合拓扑排序的背景，第4题大概率是**关键路径（CPM）**相关的问题，这是拓扑排序最常用的场景：

1. 先用拓扑排序确定节点的执行顺序
2. 计算每个节点的最早开始时间（ES）：从起点出发，按拓扑顺序，每个节点的ES是所有前驱节点的ES加上对应边权重的最大值
3. 计算每个节点的最晚开始时间（LS）：从终点倒推，每个节点的LS是所有后继节点的LS减去对应边权重的最小值
4. 关键路径就是那些ES等于LS的节点和边组成的路径，这条路径的总时长就是整个项目的最短完成时间

如果作业是其他图相关问题，比如最短路径、连通性检测，也可以基于拓扑排序的结果延伸处理。建议仔细看homework2文档里的第4题要求，结合图的基础算法来思考。

内容的提问来源于stack exchange，提问作者Julian M.