目录
1 关系: 拓撲排序。
拓撲排序
在计算机科学领域，有向图的拓扑排序或拓扑排序是其顶点的线性排序，使得对于从顶点 u 到顶点 v 的每个有向边 uv ， u 在排序中都在 v 之前。 例如，图形的顶点可以表示要执行的任务，并且边缘可以表示一个任务必须在另一个任务之前执行的约束; 在这个应用中，拓扑排序只是一个有效的任务顺序。 如果且仅当图形没有定向循环，即如果它是有向无环图（DAG），则拓扑排序是可能的。 任何 DAG 具有至少一个拓扑排序，并且已知这些算法用于在线性时间内构建任何 DAG 的拓扑排序。 在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（Topological sorting）。.