拓扑排序（Topological Sort）详解 🧠

拓扑排序是图论中的经典算法，常用于处理有向无环图（DAG）中的节点排序问题。其核心思想是：将图中的节点按依赖关系排列，确保每个节点都在其依赖节点之后。

应用场景 📈

任务调度：如编译顺序、课程安排（依赖前置课程）
依赖解析：如软件包安装顺序、构建依赖关系
数据处理：如处理有先后顺序的数据流

核心算法 🔍

1. Kahn算法（基于入度）

步骤：
1. 计算所有节点的入度
2. 将入度为0的节点加入队列
3. 依次取出队列节点，减少其邻接节点的入度
4. 重复直到队列为空

2. DFS算法（基于深度优先搜索）

步骤：
1. 从任意节点开始DFS
2. 当节点所有子节点处理完毕时，将其加入结果列表
3. 最终结果反转即为拓扑顺序

代码示例 💻

# Kahn算法示例
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 = [node for node in in_degree if in_degree[node] == 0]
    result = []
    while queue:
        node = queue.pop(0)
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return result

扩展练习 🚀

若想进一步巩固拓扑排序的理解，可尝试以下题目：

图解辅助 📊