在有向图中找出所有简单环--Johnson算法_有向图找环

作者：繁依Fanyi0 | 2024-02-06 21:02:59

踩

有向图找环

注：本算法和计算图所有结点对最短路径的Johnson算法不同。

Johnson算法由B. Johnson发表于1975年，用于在一个有向图中寻找所有简单环。时间复杂度上界为O((n+e)(c+1))，空间复杂度为O(n+e)，其中n为顶点数，e为边数，c为存在环数。在算法执行时，每两个连续的环的输出之间的时间不会超过O(n+e)。

*常用的此类算法的复杂度比较如下：

所谓的简单环，即除了第一个和最后一个顶点，其余所有顶点在路径中只出现一次。这里排除了包括像v->v这样的自循环的边和在两个顶点之间的多条边的情况。本算法沿用Tiernan算法的记号，每个简单

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