题12

题12

题目

判断有向图中是否存在回路, 除拓扑排序外, 还可以利用 ( ). (注: 涉及下节内容)
A. 求关键路径的方法
B. 求最短路径的 Dijkstra 算法
C. 深度优先遍历算法
D. 广度优先遍历算法

分析

利用深度优先遍历可以判断图 中是否存在回路。
对于无向图来说, 若深度优先遍历过程中遇到了回边, 则必定存在环; 对于有向图来说, 这条回边可能是指向深度优先森林中另一棵生成树上的顶点的弧; 但是,从有向图的某个顶点 出发进行深度优先遍历时,若在 结束之前出现一条从顶点 到顶点 的回边,且 在生成树上是 的子孙,则有向图必定存在包含顶点 和顶点 的环。

解

C