哪些方法可以判断出一个有向图是否有环_有向图判断是否有环

作者：笔触狂放9 | 2024-02-06 21:09:08

踩

有向图判断是否有环

使用深度优先遍历，若从有向图上的某个顶点u出发,在 DFS(u)结束之前出现一条从顶点v到u的边，由于v在生成树上是u的子孙，则图中必定存在包含u和v的环,因此深度优先遍历可以检测一个有向图是否有环。

拓扑排序时,当某顶点不为任何边的头时才能加入序列,存在环时环中的顶点一直是某条边的头
不能加入拓扑序列。也就是说,还存在无法找到下一个可以加入拓扑序列的顶点，则说明此图存在回路。

关键路径能否判断一个图有环,则存在一些争议。关键路径本身虽然不允许有环,但求家关键路径的算法本身无法判断是否有环,判断是否有环是求关键路径拓扑排序。

所以这个问题的答案主要取决于你从哪个角度出发看问题

（ps：求最短路径是允许图有环的。）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/64578?site