拓扑排序的定义

拓扑排序（Topological Sorting）是针对有向无环图（DAG）的一种线性排序算法，使得图中任意一条有向边 ( u \rightarrow v ) 在排序中满足 ( u ) 位于 ( v ) 的前面。这种排序常用于任务调度、依赖关系分析等场景。

适用条件

• 有向无环图（DAG）：图中不能存在环路，否则无法进行拓扑排序。
• 偏序关系：反映节点间的依赖关系，例如课程先修条件或编译顺序。

算法实现方法

Kahn 算法（基于入度）

1. 统计所有节点的入度（即有多少边指向该节点）。
2. 将入度为0的节点加入队列，并输出到排序结果中。
3. 依次处理队列中的节点，将其邻接节点的入度减1。若邻接节点入度变为0，则加入队列。
4. 重复上述过程直至队列为空。若剩余节点入度均不为0，说明图中存在环。

DFS 深度优先搜索

1. 从任意未访问的节点开始深度优先遍历。
2. 递归访问当前节点的所有邻接节点。
3. 将当前节点标记为已访问，并将其加入排序结果的头部。
4. 最终得到的逆序即为拓扑排序结果。

代码示例（Python）

Kahn 算法实现

from collections import deque

def topological_sort_kahn(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    topo_order = []
    
    while queue:
        node = queue.popleft()
        topo_order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    if len(topo_order) != len(graph):
        return None  # 存在环
    return topo_order

DFS 实现

def topological_sort_dfs(graph):
    visited = set()
    stack = []
    
    def dfs(node):
        if node in visited:
            return
        visited.add(node)
        for neighbor in graph.get(node, []):
            dfs(neighbor)
        stack.append(node)
    
    for node in graph:
        dfs(node)
    
    return stack[::-1]

应用场景

• 任务调度：确保依赖任务优先执行。
• 课程安排：处理课程先修条件。
• 编译顺序：确定源代码文件的编译顺序。
• 数据管道：管理数据处理的依赖关系。

复杂度分析

• 时间复杂度：( O(V + E) )，其中 ( V ) 为节点数，( E ) 为边数。
• 空间复杂度：( O(V) )，存储入度或递归栈。

注意事项

• 若图中存在环，拓扑排序无法完成，需提前检测环路。
• 同一张图可能有多个合法的拓扑排序结果。