拓扑排序详解（Python实现有向无环图的依赖关系排序）

拓扑排序的应用场景

• 任务调度系统（如 Makefile、Airflow）
• 课程先修要求规划
• 软件包依赖解析（如 pip、npm）
• 数据序列化与反序列化顺序

实现拓扑排序的两种常用方法

拓扑排序主要有两种经典实现方式：

1. Kahn 算法（基于入度）
2. DFS 深度优先搜索（基于递归后序遍历）

方法一：Kahn 算法（推荐给初学者）

Kahn 算法的核心思想是：

1. 计算每个节点的入度（即有多少条边指向该节点）
2. 将所有入度为 0 的节点加入队列
3. 依次从队列中取出节点，将其加入结果列表，并减少其邻居节点的入度
4. 若邻居节点入度变为 0，则将其加入队列
5. 重复直到队列为空

下面是使用 Python 实现 Kahn 算法的完整代码：

from collections import deque, defaultdictdef topological_sort_kahn(num_nodes, edges):    """    使用 Kahn 算法进行拓扑排序    :param num_nodes: 节点数量（假设节点编号为 0 到 num_nodes-1）    :param edges: 边列表，格式为 [(u, v), ...] 表示 u -> v    :return: 拓扑排序结果列表，若图中存在环则返回空列表    """    # 构建邻接表和入度数组    graph = defaultdict(list)    in_degree = [0] * num_nodes        for u, v in edges:        graph[u].append(v)        in_degree[v] += 1        # 初始化队列：所有入度为0的节点    queue = deque()    for i in range(num_nodes):        if in_degree[i] == 0:            queue.append(i)        result = []        # 处理队列    while queue:        node = queue.popleft()        result.append(node)                # 遍历当前节点的所有邻居        for neighbor in graph[node]:            in_degree[neighbor] -= 1            if in_degree[neighbor] == 0:                queue.append(neighbor)        # 如果结果长度不等于节点总数，说明图中存在环    if len(result) != num_nodes:        return []  # 存在环，无法拓扑排序        return result# 示例使用if __name__ == "__main__":    # 定义图：5个节点，边表示依赖关系    nodes = 5    edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]        order = topological_sort_kahn(nodes, edges)    if order:        print("拓扑排序结果:", order)    else:        print("图中存在环，无法进行拓扑排序！")

方法二：基于 DFS 的拓扑排序

深度优先搜索（DFS）方法通过递归遍历图，在回溯时将节点加入结果列表（即后序遍历），最后反转列表得到拓扑序。

def topological_sort_dfs(num_nodes, edges):    """    使用 DFS 进行拓扑排序    :param num_nodes: 节点数量    :param edges: 边列表    :return: 拓扑排序结果列表，若存在环则返回空列表    """    from collections import defaultdict        graph = defaultdict(list)    for u, v in edges:        graph[u].append(v)        visited = [False] * num_nodes      # 记录是否访问过    rec_stack = [False] * num_nodes    # 记录当前递归栈中的节点（用于检测环）    result = []        def dfs(node):        visited[node] = True        rec_stack[node] = True                for neighbor in graph[node]:            if not visited[neighbor]:                if dfs(neighbor):                    return True            elif rec_stack[neighbor]:                # 发现环                return True                rec_stack[node] = False        result.append(node)        return False        for i in range(num_nodes):        if not visited[i]:            if dfs(i):                return []  # 存在环        return result[::-1]  # 反转后序遍历结果

注意事项与常见误区

• 拓扑排序仅适用于有向无环图（DAG）。如果图中存在环，则无法进行拓扑排序。
• 一个 DAG 可能存在多个合法的拓扑排序结果。
• 使用 Kahn 算法时，务必检查最终结果的长度是否等于节点总数，以判断是否存在环。
• 在实际项目中，建议使用 Kahn 算法，因为它更直观、易于调试，且天然支持检测环。

总结

本文详细介绍了Python拓扑排序算法的原理与实现，包括 Kahn 算法和 DFS 方法。通过理解有向无环图的特性，我们可以高效地解决各种依赖关系排序问题。无论你是准备面试还是开发实际系统，掌握拓扑排序都是程序员的重要技能之一。

关键词回顾：拓扑排序、Python拓扑排序算法、有向无环图、依赖关系排序。