已知有向图G=(V，A)，其中V={a，b，C，d，e}，A={＜a，b＞，＜a，c＞，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞}，对该图进行拓扑排序，下面序列中()不是拓扑排序A.a，d，c，b，e B.d，a，b，c，e C.a，b，d，c，e D.a，b，c，d，e

题目
已知有向图G=(V，A)，其中V={a，b，C，d，e}，A={＜a，b＞，＜a，c＞，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞}，对该图进行拓扑排序，下面序列中()不是拓扑排序

A.a，d，c，b，e
B.d，a，b，c，e
C.a，b，d，c，e
D.a，b，c，d，e
相似考题

1.有向图G=(V，E)，其中V={a，b，c，d}，E={a，ba，d，b，c，c，d}，则图G为强连通图。()

2.设有向无环图G中的有向边集合E={,,,},则下列属于该有向图G的一种拓扑排序序列的是()。A.1,2,3,4B.2,3,4,1C.1,4,2,3D.1,2,4,3

3.下面哪个序列不是此图的一个拓扑排序()A.ebfgadchB.aebdgfchC.adchebfgD.Aedbfgch

4.对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。()此题为判断题(对，错)。

更多“已知有向图G=(V，A)，其中V={a，b，C，d，e}，A={＜a，b＞，＜a，c＞，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞}，对该图进行拓扑排序，下面序列中()不是拓扑排序”相关问题

  • 第1题：

    已知图G＝(V,E)，其中V＝(a，b，c，d，e，f)，E：{＜a，b＞，＜a，d＞，＜a，e＞，＜d，e＞，＜e， b＞，＜c，b＞，＜c，e＞，＜c，b，＜f，e＞}，则从该图的顶点a出发的深度优先遍历序列是(51)，广度优先遍历序列是(52)，其深度优先生成树(或森林)是(53)，广度优先生成树(或森林)是(54)，该图的一个拓扑序列是(55)。

    A．abdecf

    B．abdcef

    C．aebdcf

    D．adebfe


    正确答案：A
    解析：图的深度优先遍历是从图中的某个节点V1出发，访问此节点，然后依次从V1的未被访问的邻接点进行深度优先遍历，直到图中所有和V1有路径相通的节点都被访问到。若此时图中尚有节点未被访问，则选图中的一个未被访问的接点作起点。重复此过程。因此此图的深度优先遍历序列是abcdef。广度优先遍历是先访问结点V1，然后访问V1连接到的所有未被访问的结点V2，V3，，…Vt，再依次访问V2，V3，…，Vt连接到的所有未被访问的结点。如此进行下去，直到访问遍所有结点。冈此，此图的广度优先遍历序列是abdecf。对于连通图，从图的任一顶点出发进行深度优先遍历时，所经过的边与连通图的所有顶点构成的生成树为图的深度优先生成树；从图的任一顶点山发进行广度优先遍历时，所经过的边与连通图的所有顶点构成的生成树为图的广度优先生成树。对于非连通图，图中的每一个连通分量的生成树的集合为生成森林：按深度优先遍历得到的为深度优先生成森林，按广度优先遍历得到的为广度优先生成森林。因此，图G的深度优先生成森林和广度优先生成森林分别为：如果有向图的某个结点序列满足如下条件：若从结点V1到vj有一条路径，则在序列中结点Vi必定在vj之前，则称该序列是一个拓扑序列。任何无环有向图的结点都可以排在一个拓扑序列中。拓扑排序的方法是重复执行下列步骤(1)和(2)，直到所有结点均已被输出。1．从图中选择一个入度为0的结点且输出。2．从图中删除此结点及其所有的出边。在可供选择的答案中，C是一个拓扑序列。

  • 第2题：

    拓扑排序运算只能用于()

    A.带权有向图

    B.连通无向图

    C.有向无环图

    D.无向图


    正确答案：C

  • 第3题：

    拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧或存在从顶点v到w的路径，则在该有向图的任一拓扑序列中，v一定在w之前。下面有向图的拓扑序列是（ ）。

    A.41235
    B.43125
    C.42135
    D.41325

    答案：A
    解析：
    拓扑排序通俗一点来讲，其实就是依次遍历没有前驱结点的结点。而某一时刻没有前驱结点的结点有可能存在多个，所以一个图的拓扑排序可能有多个。
    4号结点没有前戏，所以拓扑排序的第一个元素是4。当4访问完了就可以访问1，1号访问完了就可以访问2，2号访问完了就可以访问3或5。所以拓扑排序结果为：412(35)。


  • 第4题：

    若已知有向图G=（V，E），其中，顶点的集合为V={v1，v2，v3，v4，v5}，弧的集合为E={， ，，，，}，则G的拓扑序列有哪些？（写出结论即可）


    正确答案:G的拓扑序列有3个，分别是v1,v2,v3,v4,v5；v1,v3,v2,v4,v5和v1,v3,v4,v2,v5。

  • 第5题：

    对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。


    正确答案:错误

  • 第6题：

    假定一个有向图的边集为{，，< c，f>，< d，c>，< e，b>，< e，d>}，对该图进行拓扑排序得到的顶点序列为（）


    正确答案:aebdcf

  • 第7题：

    已知一无向图G=（V，E），其中V={a，b，c，d，e}E={（a，b），（a，d），（a，c），（d，c），（b，e）}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是（）方法。


    正确答案:深度遍历

  • 第8题：

    单选题
    设有向无环图G中的有向边集合E={，，，}，则下列属于该有向图G的一种拓扑排序序列的是（）
    A

    1，2，3，4

    B

    2，3，4，1

    C

    1，4，2，3

    D

    1，2，4，3


    正确答案： A
    解析： 暂无解析

  • 第9题：

    判断题
    对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第10题：

    填空题
    假定一个有向图的边集为{，，，，，}，对该图进行拓扑排序得到的顶点序列为（）

    正确答案： aebdcf
    解析： 暂无解析

  • 第11题：

    填空题
    有向图G可拓扑排序的判别条件是（）。

    正确答案： 没有回路
    解析： 暂无解析

  • 第12题：

    判断题
    有回路的有向图不能完成拓扑排序。
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第13题：

    拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧或存在从顶点v到w的路径，则在该有向图的任一拓扑序列中，V一定在w之前。下面有向图的拓扑序列是( )

    A.41235

    B.43125

    C.42135

    D.41=325


    正确答案：A

  • 第14题：

    拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系。对于图中的有向图， ( ) 不是其的一个拓扑序列。

    A.1526374
    B.1526734
    C.5123764
    D.5126374

    答案：C
    解析：
    拓扑序列是将有向图中所有顶点排成一个线性序列，并且该序列满足：若在图中存在从顶点Vi到Vj的路径，则在该线性序列中，顶点i必然在顶点Vj之前。对有向图进行拓扑排序的方法如下：① 在有向图中选择一个入度为零(没有前驱)的顶点且输出之：② 从有向图中删除该顶点及从该顶点出发的所有弧；③ 重复上述两步，直至图中不存在入度为0的顶点为止。对于图3-4所示的有向图，进行拓扑排序的顶点序列有：5126374、5126734、1526374和1526734。而选项C的"5123764"不是其中的一个拓扑序列。

  • 第15题：

    拓扑排序的主要功能是什么？对于一个存在拓扑序列的有向图，通过拓扑排序得到的拓扑序列是否惟一？


    正确答案:拓扑排序的主要功能是检测一个有向图中是否存在回路。对于一个存在拓扑序列的有向图，通过拓扑排序得到的拓扑序列不一定惟一。

  • 第16题：

    通过拓扑排序能够得到拓扑序列的图一定是一个（）的图。


    正确答案:有向无环

  • 第17题：

    有回路的有向图不能完成拓扑排序。


    正确答案:正确

  • 第18题：

    有向图G可拓扑排序的判别条件是（）。


    正确答案:没有回路

  • 第19题：

    无向图G=（V，E），其中V={a，b，c，d，e，f}，E={（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

    • A、a，b，e，c，d，f
    • B、a，c，f，e，b，d
    • C、a，e，b，c，f，d
    • D、a，e，d，f，c，b

    正确答案:D

  • 第20题：

    问答题
    若已知有向图G=（V，E），其中，顶点的集合为V={v1，v2，v3，v4，v5}，弧的集合为E={， ，，，，}，则G的拓扑序列有哪些？（写出结论即可）

    正确答案： G的拓扑序列有3个，分别是v1,v2,v3,v4,v5；v1,v3,v2,v4,v5和v1,v3,v4,v2,v5。
    解析： 暂无解析

  • 第21题：

    单选题
    无向图G＝（V，A），其中V＝｛a，b，c，d，e｝， A={，，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞} 对该图进行扑拓排序，下面序列中（）不是拓扑序列。
    A

    adcbe

    B

    dabce

    C

    abdce

    D

    abcde


    正确答案： B
    解析： 暂无解析

  • 第22题：

    问答题
    拓扑排序的主要功能是什么？对于一个存在拓扑序列的有向图，通过拓扑排序得到的拓扑序列是否惟一？

    正确答案： 拓扑排序的主要功能是检测一个有向图中是否存在回路。对于一个存在拓扑序列的有向图，通过拓扑排序得到的拓扑序列不一定惟一。
    解析： 暂无解析

  • 第23题：

    填空题
    已知一无向图G=（V，E），其中V={a，b，c，d，e}E={（a，b），（a，d），（a，c），（d，c），（b，e）}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是（）方法。

    正确答案： 深度遍历
    解析： 暂无解析

相关内容