题11

题11

题目

Q:下面的 ( ) 方法可以判断出一个有向图是否有环 (回路).
I. 深度优先遍历
II. 拓扑排序
III. 求最短路径
IV. 求关键路径
A. I、II、IV
B. I、III、IV
C. I、 II、III
D. 全部可以

分析

A:我觉得一二三都可以，但是答案是一二四可以，3却不行，这是因为求最短路径是为了找到最短路径，而不是判断是否有环，所以不行。

解

A
使用深度优先遍历,若从有向图上的某个顶点 出发,在 结束之前出现一条从顶点 到 的边,由于 在生成树上是 的子孙,图中必定存在包含 和 的环,因此深度优先遍历可以检测一个有向图是否有环。
拓扑排序时, 当某顶点不为任何边的头时才能加入序列, 存在环时环中的顶点一直是某条边的头, 不能加入拓扑序列。
也就是说, 还存在无法找到下一个可以加入拓扑序列的顶点, 则说明此图存在回路。
求最短路径是允许图有环的。
至于关键路径能否判断一个图有环, 则存在一些争议。
关键路径本身虽然不允许有环, 但求关键路径的算法本身无法判断是否有环, 判断是否有环是求关键路径的第一步:拓扑排序。