拓扑排序

拓扑排序是针对有向无环图（DAG）的一种排序算法，它能够输出一个线性的序列。该序列满足如果存在一条从顶点A到顶点B的路径，那么在序列中B出现在A的后面。这种排序方法可以用于确定任务执行顺序或判断事件因果关系等场景。拓扑排序的基本思想是对DAG中的每个顶点进行深度优先搜索，并在搜索过程中记录每个顶点的入度。当所有顶点的入度都为0时，就可以得到一个拓扑有序的序列。由于DAG可能存在环，因此并不是所有的DAG都能够得到拓扑有序序列。如果DAG中存在环，则不存在拓扑有序序列。