图的拓扑排序序列是唯一的嘛

拓扑排序，作为图论中的一个经典问题，具有广泛的应用价值。在实际场景中，拓扑排序可以被用于任务调度、数据流分析、课程安排等领域。一般来说，拓扑排序会输出一个有向无环图（DAG）的拓扑排列顺序。然而，许多人会问：图的拓扑排序序列是唯一的吗？在本文中，我们将从几个角度探究这个问题。

首先，我们需要了解什么是拓扑排序。在一个有向无环图中，如果对于每个有向边 (u, v)，顶点 u 都排在顶点 v 的前面，那么这个图就被称为拓扑有序的。拓扑排序就是把拓扑有序的图转化成一个线性序列的过程，这个线性序列就被称为拓扑排序序列。一般来说，拓扑排序可以通过深度优先遍历或广度优先遍历实现。

那么，图的拓扑排序序列是否唯一呢？下面从几个角度进行分析。

角度一：图的拓扑排序序列可能不唯一

首先，我们需要了解一个事实：对于一个有向无环图（DAG），有多个拓扑排序序列的前提条件是有至少两个入度为 0 的顶点。比如下图：


在这个图中，我们可以发现顶点 A 和 B 同时入度为 0，因此我们有两种情况：

- A -> B -> C -> D -> E

- B -> A -> C -> D -> E

这两种情况都是合法的拓扑排序序列，因此我们可以得出结论：图的拓扑排序序列可能不唯一。

角度二：图的拓扑排序序列在某些情况下是唯一的

虽然有时候图的拓扑排序序列不唯一，但是在某些情况下，它却是唯一的。为了分析这个问题，我们需要了解一个概念：拓扑有序图上的“最小元素”。

在一个有向无环图（DAG）中，如果一个顶点没有前驱顶点，那么它就是该图上的“最小元素”。显然，如果有两个“最小元素”，那么图的拓扑排序序列就不唯一。但是，在只有一个“最小元素”的情况下，图的拓扑排序序列就是唯一的。

比如下图：


在这种情况下，顶点 A 是唯一的“最小元素”，因此图的拓扑排序序列就是 A -> B -> C -> D -> E。可以发现，这个序列是唯一的，因为不存在其他的“最小元素”。

角度三：有向图的全序关系

除了上述角度外，我们还可以从一个更加理论的角度来分析这个问题。前面提到，拓扑排序的结果是一个线性序列。在数学中，线性序列也被称为全序集。

因此，我们需要了解什么是全序关系。在集合论中，如果一个集合 S 上有一个二元关系 <=，满足下列三个性质：

- 自反性：对于任意的 a ∈ S，都有 a <= a。

- 反对称性：如果 a <= b 且 b <= a，那么 a = b。

- 传递性：对于任意的 a, b, c ∈ S，如果 a <= b 且 b <= c，那么 a <= c。

那么，我们就可以称关系 <= 是 S 上的一个全序关系。可以证明，对于一个有向无环图（DAG），它的拓扑排序序列就是该图上的全序关系。

根据上面的定义，我们可以证明，有向无环图的拓扑排序序列是唯一的，当且仅当该图上存在一个全序关系。