有向无环图

有向无环图(Directed Acyclic Graph) link

graph TB
subgraph Directed Acyclic Graph
  direction TB
  A((0))
  B((1))
  C((2)) --> D
  D((3)) --> B
  E((4)) --> A
  F((5)) --> A
  F --> C
  E --> B
end

拓扑排序 link

在有向无环图(DAG)中，若一条边确定由A指向B，则遍历结果中A将始终排在B的前面的排序方式称为拓扑排序。它的核心思想是跟踪顶点的入度(In Degree), 当入度为0时可以访问当前节点(代表当前顶点的前驱顶点已经访问完毕)，访问当前节点之后对邻接顶点的入度减1，循环迭代直至所有节点入度为0。我们可以使用队列存储入度为0的顶点，当对邻接顶点入度减少到0是入队，队列为空时代表所有节点入度为0。

若希望找到所有的拓扑排序，需要配合递归和回溯思想。每次遍历取入度为0且未被发现的顶点v，更新v的的邻接顶点的入度，添加v到路径列表path，然后进行归查找。函数在达到递归最深层时(所有节点被发现)，准备返回时判断path的长度等于顶点数量则输出路径到结果。当递归返回时需要恢复v邻接顶点的入度，并将v从l中移除。