无"超前访问"的有向无环图遍历方法求解

你需要的是拓扑排序的特定实现——保证遍历序列中所有依赖边（箭头）的起点编号小于终点编号，核心是在选择下一个可访问节点时，优先挑选当前入度为0的节点里编号最小的那个。

为什么普通DFS/BFS行不通？ #

普通DFS会优先沿着某条分支深度遍历，可能提前选中左侧分支的节点，破坏编号递增的依赖约束；普通BFS按层处理节点，同样无法保证只挑选编号最小的可用节点，自然得不到符合要求的序列。

具体实现步骤 #

• 先计算每个节点的入度：统计有多少个前置节点指向当前节点。
• 用**最小堆（优先队列）**存储所有入度为0的节点，堆的特性会自动把编号最小的节点放在顶部。
• 循环执行以下操作直到堆为空：
  1. 取出堆顶的节点，加入最终遍历序列。
  2. 遍历该节点的所有邻接节点（即被当前节点指向的节点），把它们的入度减1。
  3. 如果某个邻接节点的入度减到0，就将它加入最小堆。

示例说明 #

假设你的图结构是：节点1→4，节点2→4，节点3→5，节点4→5。

1. 初始入度：1(0)、2(0)、3(0)、4(2)、5(2)
2. 最小堆初始放入1、2、3，取出编号最小的1，序列变为[1]；将4的入度减为1。
3. 堆中剩下2、3，取出2，序列变为[1,2]；将4的入度减为0，把4加入堆。
4. 堆中剩下3、4，取出3，序列变为[1,2,3]；将5的入度减为1。
5. 堆中剩下4，取出4，序列变为[1,2,3,4]；将5的入度减为0，把5加入堆。
6. 取出5，最终序列是[1,2,3,4,5]，完全符合箭头从小编号指向大编号的要求。

这种方法既严格遵守了依赖关系（只有前置节点都访问过才会处理当前节点），又保证了编号的递增约束，完美解决你遇到的问题。

内容的提问来源于stack exchange，提问作者Sventies