1、拓扑排序算法可以用于判断给定无向图是否有环。

题目

1、拓扑排序算法可以用于判断给定无向图是否有环。

相似考题

1.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用()。A、求关键路径的方法B、求最短路径的Dijkstra方法C、宽度优先遍历算法D、深度优先遍历算法

2.下面()方法可以判断出一个有向图是否有环。A.深度优先遍历B、拓扑排序C.求最短路径D、求关键路径

3.拓扑排序算法仅适用于有向无环图。()

4.采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路)()A.对B.错

更多“1、拓扑排序算法可以用于判断给定无向图是否有环。”相关问题

  • 第1题：

    采用邻接表存储的图的深度优先遍历算法类似于树的(22)，用邻接表存储的图的广度优先遍历算法类似于树的(23)，判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用(24)。

    A．中序遍历

    B．先序遍历

    C．后序遍历

    D．按层次遍历


    正确答案：B
    解析：采用邻接表存储的图的深度优先遍历算法类似于树的先序遍历。

  • 第2题：

    在对有向无环图执行拓扑排序算法之后,入度数组中所有元素的值均为0。()

    此题为判断题(对，错)。


    参考答案：对

  • 第3题：

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

    A.带权有向图

    B.连通无向图

    C.有向无环图

    D.无向图


    正确答案：C

  • 第4题：

    判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。

    A.求关键路径的方法
    B.求最短路径的Dijkstra方法
    C.广度优先遍历算法
    D.深入度优先遍历算法

    答案：D
    解析：
    判断一个图是否存在回路的方法包括：(1)设图G是n个顶点的无向图，若G的边数e＞=n，则图G中一定有回路存在。(2)设图G是n个顶点的无向连通图，若G的每个顶点的度＞=2，则图G中一定有回路存在。(3)利用拓扑排序算法可以判断图中是否存在回路。即在拓扑排序输出结束后所余下的顶点均有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在有回路。(4)利用深度优先遍历算法可以判定图G中是否存在回路。对于无向图来说，若深度优先遍历过程中遇到了回边则必定存在环；对于有向图来说，这条回边可能是指向深度优先森林中另一棵生成树上顶点的弧；但是，如果从有向图上的某个项点v出发进行深度优先遍历，若在dfs(v)结束之前出现一条认顶点v到顶点v的回边，因u在生成树上是v的孙子，则有向图必定存在半含顶点u和顶点v的环。

  • 第5题：

    下面（）可以判断出一个有向图中是否有环（回路）。

    • A、广度优先遍历
    • B、拓扑排序
    • C、求最短路径
    • D、求关键路径

    正确答案:B

  • 第6题：

    对于一个有向图，不用拓扑排序，如何判定图中是否存在环？


    正确答案:对于无向图，如果在深度优先遍历中遇到回边，则必定存在环。对于有向图，如果从有向图的某个顶点v出发的遍历，在DFS(v)结束之前出现了一条从顶点u指向v的回边，则此有向图必定存在环。因为u在深度优先生成树上是v的子树，即存在u到v的路径，现在又出现一条从u指向v的弧，则它们必然构成一条回路。

  • 第7题：

    下面（）方法可以判断出一个有向图是否有环。

    • A、深度优先遍历
    • B、拓扑排序
    • C、求最短路径
    • D、求关键路径

    正确答案:B

  • 第8题：

    判断题
    任何无环的有向图，其结点都可以排在一个拓扑序列里。
    A

    对

    B

    错


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

  • 第9题：

    单选题
    下列方法中可以判断出一个有向图是否有环（回路）的是（  ）。
    A

    广度优先遍历

    B

    拓扑排序

    C

    求最短路径

    D

    求关键路径


    正确答案： A
    解析：

  • 第10题：

    单选题
    下面（）方法可以判断出一个有向图是否有环。
    A

    深度优先遍历

    B

    拓扑排序

    C

    求最短路径

    D

    求关键路径


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

  • 第11题：

    单选题
    一个有向无环图的拓扑排序序列（）是唯一的。
    A

    一定

    B

    不一定

    C

    不可能

    D

    无法判断


    正确答案： D
    解析：

  • 第12题：

    单选题
    下面（）可以判断出一个有向图中是否有环（回路）。
    A

    广度优先遍历

    B

    拓扑排序

    C

    求最短路径

    D

    求关键路径


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

  • 第13题：

    对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。()

    此题为判断题(对，错)。


    正确答案：正确

  • 第14题：

    设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。

    若有向图采用邻接矩阵表示(例如，图4-1所示有向图的邻接矩阵如图4-3所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时问复杂度是(7)。


    正确答案：(6)O(n+e) (7)O(n2)
    (6)O(n+e) (7)O(n2) 解析：邻接表：对有n个顶点和e条弧的有向图而言，在拓扑排序中，若有向图无环，则每个顶点进出队列各一次，共执行e次，搜索算法时间复杂度是由n和e共同决定的，所以总的时间复杂度为O(n+e)。
    当用邻接矩阵：对于每个顶点，查找相邻边的时间复杂度是O(n)，一共有n个顶点，所以总的时间复杂度是O(n2)。

  • 第15题：

    判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用______。

    A．求关键路径的方法

    B．求最短路径的Dijkstra方法

    C．深度优先遍历算法

    D．广度优先遍历算法


    正确答案：C
    解析：本题考查AOV的运算，要检测一个工程是否可行，首先就应检查对应的AOV网是否存在回路，检测的一种方法就是对有向图构造其顶点的拓扑有序序列，而对AOV网进行拓扑排序主要考虑顶点的入度，相应的，若在AOV网中考查各项点的出度，这种排序就称为逆排序。同时，还可以利用深度优先遍历进行拓扑排序，因为图中无环，则由图中某点出发进行深度优先遍历时，最先退出DFS函数的顶点即是出度为零的顶点，它是拓扑有序序列中最后的一个顶点。由此，按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。

  • 第16题：

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


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

  • 第17题：

    下面哪一个方法可以判断出一个有向图中是否有环回路（）

    • A、深度优先遍历
    • B、拓扑排序
    • C、求最短路径
    • D、求关键路径

    正确答案:A,B

  • 第18题：

    判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用（）。

    • A、求关键路径的方法
    • B、求最短路径的Dijkstra方法
    • C、深度优先遍历算法
    • D、广度优先遍历算法

    正确答案:C

  • 第19题：

    下面哪一方法可以判断出一个有向图是否有环（回路）（）。

    • A、求节点的度
    • B、拓扑排序
    • C、求最短路径
    • D、求关键路径

    正确答案:B

  • 第20题：

    单选题
    用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（  ）。
    A

    逆拓扑有序

    B

    拓扑有序

    C

    无序的

    D

    无法判断


    正确答案： B
    解析：

  • 第21题：

    单选题
    判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用（）。
    A

    求关键路径的方法

    B

    求最短路径的Dijkstra方法

    C

    深度优先遍历算法

    D

    广度优先遍历算法


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

  • 第22题：

    单选题
    下面哪一方法可以判断出一个有向图是否有环（回路）（）。
    A

    求节点的度

    B

    拓扑排序

    C

    求最短路径

    D

    求关键路径


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

  • 第23题：

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

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

  • 第24题：

    问答题
    对于一个有向图，不用拓扑排序，如何判定图中是否存在环？

    正确答案： 对于无向图，如果在深度优先遍历中遇到回边，则必定存在环。对于有向图，如果从有向图的某个顶点v出发的遍历，在DFS(v)结束之前出现了一条从顶点u指向v的回边，则此有向图必定存在环。因为u在深度优先生成树上是v的子树，即存在u到v的路径，现在又出现一条从u指向v的弧，则它们必然构成一条回路。
    解析： 暂无解析

相关内容