己知有向图G=(V,A),其中V={a,b,c,d,e),A={
,
,
,
,
,
},对该图进行拓扑排序,下面序列中不是拓扑排序的是( )。
A、
a,d,c,b,e
B、
d,a,b,c,e
C、
a,b,d,c,e
D、
a,b,c,d,e
【正确答案】
D
【答案解析】
解析:考查拓扑排序。拓扑排序的方法:1)从AOV网中选择一个没有前驱的顶点(入度为0),并输出它;2)从AOV网中删去该顶点,以及从该顶点发出的全部有向边;3)重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止。选项D中,删去a、b及其对应的出边后,c的入度不为0,此有边<(d,c>,故不是拓扑序列。选项A、B、D均为拓扑序列。解答本类题时,建议读者根据边集合画出草图。
提交答案
关闭