拓扑排序的具体实例

本文主要是介绍拓扑排序的具体实例，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

以下是一个拓扑排序的具体实例，我们将通过一个有向无环图（DAG）来说明如何进行拓扑排序。

假设我们有以下的有向无环图：

   A/ \B   C\ /D|E

在这个图中，顶点A有两个指向B和C的边，B和C都指向D，然后D指向E。这个图没有环，因此可以进行拓扑排序。

拓扑排序的步骤

1、计算所有顶点的入度：

A: 0（没有边指向A）
B: 1（有一条边A->B）
C: 1（有一条边A->C）
D: 2（有两条边B->D和C->D）
E: 1（有一条边D->E）

2、将所有入度为0的顶点加入队列：
队列: [A]
进行拓扑排序：
（1）从队列中取出A，加入结果序列，并更新A的邻接点的入度。
结果序列: [A]
更新后入度: B: 0, C: 0, D: 2, E: 1
队列更新: [B, C]
（2）从队列中取出B，加入结果序列，并更新B的邻接点的入度。
结果序列: [A, B]
更新后入度: C: 0, D: 1, E: 1
队列更新: [C, D] （注意：虽然D的入度不为0，但C的入度已经为0，所以C先被处理）
（3）从队列中取出C，加入结果序列，并更新C的邻接点的入度。
结果序列: [A, B, C]
更新后入度: D: 0, E: 1
队列更新: [D, E]
（4）从队列中取出D，加入结果序列，并更新D的邻接点的入度。
结果序列: [A, B, C, D]
更新后入度: E: 0
队列更新: [E]
（5）从队列中取出E，加入结果序列。
结果序列: [A, B, C, D, E]
此时队列为空，排序完成。
拓扑排序的结果
因此，这个图的拓扑排序结果之一为 [A, B, C, D, E]。需要注意的是，拓扑排序的结果可能不是唯一的，只要它满足图中所有边的方向性即可。例如，[A, C, B, D, E] 也是这个图的一个有效的拓扑排序结果。