拓扑排序
Kahn 算法
输出字典序最小的topsort
你可以直接使用这段文字，它简洁地概括了“字典序最小拓扑排序”的本质：
💡 核心总结：如何实现字典序最小的拓扑排序？
1. 核心工具：
将标准 Kahn 算法中的“队列”替换为**“小根堆（优先队列）”**。
2. 算法本质：
- 入度为 0 是前提：只有当一个节点的入度减为 0 时，才意味着它所有的前驱节点都已删除完毕。此时，该节点才具备进入序列的“资格”。
- 贪心策略是关键：在任何时刻，所有入度为 0 的节点都是彼此独立、可以随时输出的。为了让整体字典序最小，我们每次都从这群“自由节点”中，利用小根堆挑出编号最小的那一个优先输出。
3. 一句话证明：
- 由于进入堆的节点前驱已全部清空，它们之间不存在先后约束，因此“每一步都选最小的”这一局部最优解，最终会导向全局字典序最小的拓扑序。
- 进入堆是“前驱已全部删除”的充分必要条件。
dfs输出所有topsort
为了能求出所有的可能的topsort,这里使用dfs回溯法
-
类似 [走迷宫], 在一个分叉口,每个分叉的路线,我们都走一遍.
-
当回溯到这个路口的时候,我们要保证: 恢复现场,就像时间回溯到事情的开始,我们从新做一次选择.