题目

已给下图，哪一项是该图的拓扑排序序列（ )

（1）1，2，3，4，5
（2）1，3，2，4，5
（3）1，2，4，3，5
（4）1，2，3，5，4

答案

（1）1，2，3，4，5

拓扑排序

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。 [2]

本题中，入度为 0 的顶点是 1；
删除1 后，入度为 0 的顶点是 2；
删除 2 后，入度为 0 的顶点是 3;
删除 3 后，入度为 0 的顶点是 4;
删除 4 后，入度为 0 的顶点是 5;