基于源移除算法的拓扑排序代码陷入无限循环无输出求助

我来帮你分析这个拓扑排序的无限循环问题～首先明确你的场景：你用源移除算法实现拓扑排序，用邻接矩阵表示4个顶点的有向无环图（DAG），预期输出拓扑序是1 2 3 4，但代码陷入无限循环连第一个顶点都没输出，参考的原代码循环部分也有问题。

先拆解你的图结构 #

你的邻接矩阵对应的图是：

• 顶点1 → 顶点2、顶点3
• 顶点2 → 顶点4
• 顶点3 → 顶点4
• 顶点4无出边
  这确实是一个DAG，存在合法拓扑序（比如1 2 3 4或1 3 2 4都是正确的）。

无限循环的核心原因推测 #

源移除算法的核心是跟踪顶点的入度，每次找到入度为0的“源点”，移除它并更新邻接顶点的入度。你的代码大概率在以下环节出错了：

• 入度计算/维护错误：要么初始入度算错，要么移除源点后没正确更新邻接顶点的入度；
• 未标记已处理的顶点：重复计算已移除顶点的入度，导致永远找不到新的源点；
• 循环逻辑漏洞：没判断“找不到源点”的情况，导致在无合法源点时一直循环。

错误代码示例（类似你可能的写法） #

比如很多新手会犯的错误：直接遍历邻接矩阵计算入度，但没排除已处理的顶点，或者更新出边的方式不对：

n = 4
adj = [
    [0,1,1,0],
    [0,0,0,1],
    [0,0,0,1],
    [0,0,0,0]
]
top_order = []
while len(top_order) < n:
    # 错误：计算入度时没排除已处理顶点
    found = -1
    for i in range(n):
        in_degree = sum(adj[j][i] for j in range(n))
        if in_degree == 0:
            found = i
            break
    if found == -1:
        break
    top_order.append(found+1)
    # 错误：仅清空源点的出边，但没更新邻接顶点的入度
    adj[found] = [0]*n

这段代码的问题是：移除源点后，邻接顶点的入度还是包含了已移除顶点的边，比如顶点1（0-based0）被移除后，顶点2的入度依然会计算到顶点0的边，导致入度永远不为0，循环一直找不到下一个源点，陷入死循环。

修正后的正确代码 #

下面是修复后的代码，每一步都明确维护入度和处理状态：

n = 4
# 0-based邻接矩阵
adj = [
    [0, 1, 1, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
]

# 1. 初始化入度数组：计算每个顶点的初始入度
in_degree = [0] * n
for col in range(n):
    for row in range(n):
        if adj[row][col] == 1:
            in_degree[col] += 1

top_order = []
processed = [False] * n  # 标记顶点是否已被处理

while len(top_order) < n:
    # 2. 寻找未处理且入度为0的源点
    source = -1
    for i in range(n):
        if not processed[i] and in_degree[i] == 0:
            source = i
            break
    
    if source == -1:
        print("图中存在环，无法完成拓扑排序")
        break
    
    # 3. 将源点加入拓扑序
    top_order.append(source + 1)  # 转成1-based编号
    processed[source] = True
    
    # 4. 更新源点所有邻接顶点的入度
    for neighbor in range(n):
        if adj[source][neighbor] == 1 and not processed[neighbor]:
            in_degree[neighbor] -= 1

# 输出结果
print("拓扑排序结果:", ' '.join(map(str, top_order)))

运行这段代码会输出1 2 3 4（或1 3 2 4，取决于源点查找的顺序，都是合法的）。

关键修复点说明 #

• 入度数组维护：初始正确计算每个顶点的入度，每次移除源点后，将其邻接顶点的入度减1，确保后续能找到新的源点；
• 处理标记：用processed数组避免重复处理已移除的顶点；
• 循环终止判断：当找不到源点时，判断为有环并退出，避免无限循环。

排查你的代码的步骤 #

如果你要自己调试，可以按以下顺序检查：

• 打印初始入度数组，看是否正确（你的图初始入度应该是[0,1,1,2]）；
• 在循环中打印每次查找的源点，看是否能找到第一个源点（顶点1，0-based0）；
• 检查移除源点后，邻接顶点的入度是否正确更新（比如移除顶点1后，顶点2和3的入度应该变为0）。

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