拓扑排序 (Topological Sort)

1. 定义与核心功能

对 DAG（有向无环图）的顶点进行线性排序，使得每条有向边 在序列中满足 在 之前。

• 偏序线性化：解决任务调度、编译依赖等”先修课程”类问题
• 环路检测：若输出序列长度小于节点总数，说明图中存在环

2. 核心数据结构

• inDegree[i]（入度数组）：记录节点 的剩余前置依赖数，inDegree[i] == 0 时节点就绪
• Queue（就绪队列）：存储当前所有入度为 0、可立即处理的节点
• Graph（邻接表）：快速查找节点 的所有后继节点

3. 算法步骤（Kahn’s Algorithm）

1. 初始化

   • 遍历全图，统计每个节点的初始入度
   • 将所有入度为 0 的节点加入队列

2. 迭代处理

   • 取出队头节点 ，加入结果列表
   • 遍历 的所有后继节点 ，执行 inDegree[m]--
   • 若 inDegree[m] 减为 0，将 加入队尾

3. 结果判定

   • 输出节点数等于顶点总数 → 排序成功
   • 否则 → 图中存在环

4. 进阶：逆向填充（DFS 实现）

DFS 实现拓扑排序时，节点在其所有后继节点处理完毕后才被记录，因此天然得到逆序结果。标准做法是维护指针 index = totalNodes - 1，每次将完成的节点放入 result[index]，然后 index--，最终 result 即为正向拓扑序。

5. 复杂度分析

	复杂度	说明
时间		每个顶点入队出队一次（），每条边扫描一次（）
空间		入度数组和队列占 ，邻接表占

字典序最小的拓扑排序：将 Queue 替换为 Min-Heap（优先队列）即可。