对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是()。

admin2015-12-30 28

问题对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是()。

选项 A、3，1，2，4，5，6
B、3，1，2，4，6，5
C、3，1，4，2，5，6
D、3，1，4，2，6，5

答案D

解析按照拓扑排序的算法，每次都选择入度为0的结点从图中删去，此图中一开始只有结点3的入度为0；删掉结点3后，只有结点1的入度为0；删掉结点1后，只有结点4的入度为0；删掉结点4后，结点2和结点6的入度都为0，此时选择删去不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为3，1，4，2，6，5和3，1，4，6，2，5，选D。