什么是拓扑排序？

在计算机科学领域，有向图的拓扑排序是其顶点的线性排序，使得对于从顶点u到顶点v的每个有向边uv，u在排序中都在v之前。例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束; 在这个应用中，拓扑排序只是一个有效的任务顺序。 如果且仅当图形没有定向循环，即如果它是有向无环图（DAG），则拓扑排序是可能的。任何DAG具有至少一个拓扑排序，并且已知这些算法用于在线性时间内构建任何DAG的拓扑排序。