为什么我的DFS拓扑排序算法执行结果与有向图设定不符？

1. 你的预期结果不符合DFS遍历逻辑 #

你给出的graph1中，起始节点Comp Sci的邻接节点包含Structures和GPU两个节点，普通DFS遍历会处理当前节点的所有未访问邻接节点，而非仅遍历单条链路：

• 走完Structures -> Algebra -> COB分支回溯到Structures后，会继续处理Structures的另一个邻接节点Digital Design，进而遍历到Compilers
• 处理完Structures全部分支回溯到Comp Sci后，会继续处理Comp Sci的另一个邻接节点GPU，进而遍历到Networking
  这就是你返回结果中存在额外节点的核心原因，你的有向图定义没有问题，是你对DFS遍历的逻辑理解有误。

2. 代码存在Python可变默认参数陷阱 #

你定义函数时用了path=[]作为默认参数，列表属于Python可变对象，该默认值只会在函数定义阶段初始化一次，多次调用函数时会复用同一个列表对象，导致多次调用的结果互相污染。修正方式是将默认参数设为None，在函数内部初始化路径：

def dfs_recursive(graph, vertex, path=None):
    if path is None:
        path = []
    path += [vertex]
    for neighbor in graph[vertex]:
        if neighbor not in path:
            path = dfs_recursive(graph, neighbor, path)
    return path

3. 现有代码不是拓扑排序实现 #

你当前的代码只是普通的前序DFS遍历，不符合拓扑排序的实现逻辑。正确的DFS版本拓扑排序需要标记节点的三种状态（未访问、访问中、已访问），在节点的所有后继节点都处理完成后再将节点加入结果栈，最终将栈倒序得到拓扑序，实现参考如下：

def topological_sort_dfs(graph):
    visited = {node: 0 for node in graph} # 0=未访问，1=访问中，2=已访问
    result = []
    
    def dfs(node):
        if visited[node] == 1:
            raise ValueError("图存在环，无法进行拓扑排序")
        if visited[node] == 2:
            return
        visited[node] = 1
        for neighbor in graph[node]:
            dfs(neighbor)
        visited[node] = 2
        result.append(node)
    
    for node in graph:
        if visited[node] == 0:
            dfs(node)
    return result[::-1]

如果要获取从Comp Sci出发可达节点的拓扑序，可以对上述返回的全量拓扑序过滤，仅保留从Comp Sci出发DFS可达的节点即可。

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