使用深度优先遍历,若从有向图上的某个顶点u出发,在 DFS(u)结束之前出现一条从顶点v到u的边,由于v在生成树上是u的子孙,则图中必定存在包含u和v的环,因此深度优先遍历可以检测一个有向图是否有环。
拓扑排序时,当某顶点不为任何边的头时才能加入序列,存在环时环中的顶点一直是某条边的头
不能加入拓扑序列。也就是说,还存在无法找到下一个可以加入拓扑序列的顶点,则说明此图存在回路。
关键路径能否判断一个图有环,则存在一些争议。关键路径本身虽然不允许有环,但求家关键路径的算法本身无法判断是否有环,判断是否有环是求关键路径拓扑排序。
所以这个问题的答案主要取决于你从哪个角度出发看问题文章来源:https://www.toymoban.com/news/detail-522143.html
(ps:求最短路径是允许图有环的。)文章来源地址https://www.toymoban.com/news/detail-522143.html
到了这里,关于哪些方法可以判断出一个有向图是否有环的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!