itgle.com
更多“判定一个有向图中是否存在回路可以利用(52)方法。A.求最小生成树B.求最短路径C.拓扑排序D.图的遍 ”相关问题
  • 第1题:

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

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

    答案:B
    解析:
    当有向图中无回路时,从某顶点出发进行深度优先遍历时,出栈的顺序(退出DFSTraverse算法)即为逆向的拓扑序列。

  • 第2题:

    下面哪一方法可以判断出一个有向图是否有环(回路):()

    A.广度优先遍历

    B.拓扑排序

    C.求最短路径

    D.求关键路径


    拓扑排序

  • 第3题:

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

    A.求关键路径的方法

    B.求最短路径的迪杰斯特拉(Dijkstra)方法

    C.广度优先遍历算法

    D.深度优先遍历算法


    深度优先遍历算法?拓扑排序

  • 第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.求关键路径


    AB