拓扑排序的DFS实现方法

题目描述
拓扑排序是一种对有向无环图（DAG）的顶点进行线性排序的方法，使得对于任何从顶点u到顶点v的有向边，u在排序中都出现在v之前。除了基于BFS的Kahn算法外，拓扑排序还可以通过深度优先搜索（DFS）实现。这种方法通过DFS遍历图，并在回溯过程中将顶点加入结果列表。

核心思想
DFS实现拓扑排序的关键在于利用DFS的递归特性：当从一个顶点出发完成所有相邻顶点的访问后，该顶点不会再有未被处理的后续顶点，此时将其加入结果列表的头部，就能保证依赖关系被正确维护。

详细步骤

1. 数据结构准备

   • 创建visited数组：记录每个顶点的访问状态（未访问/访问中/已完成）
   • 创建result栈：存储拓扑排序结果（后进先出保证顺序）
   • 创建adjacency list：图的邻接表表示

2. DFS遍历过程

   • 对每个未访问顶点调用DFS递归函数：
     • 将当前顶点标记为"访问中"状态
     • 递归访问所有未访问的相邻顶点
     • 如果遇到"访问中"的相邻顶点，说明存在环，立即报错
     • 完成所有相邻顶点访问后，将当前顶点标记为"已完成"并压入结果栈

3. 环检测机制

   • 三种顶点状态：
     • 0: 未访问
     • 1: 访问中（当前DFS路径正在处理）
     • 2: 已完成（已加入结果栈）
   • 如果在递归过程中遇到状态为1的相邻顶点，说明发现后向边，存在环

具体实现示例
考虑有向图：0→1→2，0→3

def topological_sort_dfs(graph):
    n = len(graph)
    visited = [0] * n  # 0=未访问, 1=访问中, 2=已完成
    result = []
    
    def dfs(u):
        if visited[u] == 1:  # 发现环
            raise ValueError("图中有环，无法进行拓扑排序")
        if visited[u] == 2:  # 已处理完成
            return
        
        visited[u] = 1  # 标记为访问中
        for v in graph[u]:
            dfs(v)
        visited[u] = 2  # 标记为已完成
        result.append(u)
    
    for i in range(n):
        if visited[i] == 0:
            dfs(i)
    
    return result[::-1]  # 反转得到正确顺序

# 测试用例
graph = [[1, 3], [2], [], []]  # 邻接表
print(topological_sort_dfs(graph))  # 输出：[0, 3, 1, 2]

算法特性分析

• 时间复杂度：O(V+E)，每个顶点和边只处理一次
• 空间复杂度：O(V)，用于visited数组和递归栈
• 稳定性：对于同一DAG可能产生不同但都有效的拓扑排序
• 环检测：能准确检测图中是否存在环

与Kahn算法对比

• DFS实现：递归深度可能较大，但代码简洁
• Kahn算法：需要维护入度表，更适合并行处理
• 两者时间复杂度相同，都是拓扑排序的有效方法

这种DFS实现方法不仅提供了拓扑排序的另一种视角，还展示了如何利用DFS的递归特性来处理顶点间的依赖关系，是理解图算法递归思维的重要案例。