问题 单项选择题

任意一个有向图的拓扑序列 (33)

A.可能不存在

B.有一个

C.一定有多个

D.有一个或多个

答案

参考答案:A

解析:

[分析]:
本题考查有向图的拓扑序列结构。
在有向图中,拓扑序列是通过拓扑排序后得到的所有结点的序列,拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。例如,一个软件专业的学生要修课,但有些是基础课,它独立于其他课程,而有些课程必须要在修完某些专业课后才能修,这样各课程之间就形成了一种并立与优先的关系,有向图和它的拓扑序列可以表示这样的关系。
对有向图进行拓扑排序的方法是:
(1)在有向图中任选一个没有前驱的结点且输出;
(2)从图中删除该结点和所有以它为尾的弧。
重复上述两步,直到全部顶点均已输出,或当前图中不存在无前驱的结点为止。
根据上述的说明我们可以知道,有向图的拓扑序列可能有一个或多个,但在有向图中出现有向环时,因为环意味着某项活动应该以自己为先决条件,在拓扑排序时,环中的结点是不能被排在序列中的,因此,不存在此有向图的拓扑序列。所以,对任意一个有向图而言,其拓扑序列可能不存在,也可能有一个或多个。

选择题
单项选择题