2. 考研
  3. 己知有向图G=(V，A)，其中V={a,b,c,d,e)，A={，，，，，}，对该图进行拓扑排序，下面序列中不是拓扑排序的是( )。

己知有向图G=(V，A)，其中V={a,b,c,d,e)，A={，，，，，}，对该图进行拓扑排序，下面序列中不是拓扑排序的是( )。

admin2018-09-11  35
问题 己知有向图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均为拓扑序列。解答本类题时，建议读者根据边集合画出草图。
转载请注明原文地址:https://kaotiyun.com/show/ZqRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)