我已经试用了tarjan的循环检测算法，并从http://learn.yancyparedes.net/2012/03/strongly-connected-components-using-tarjans-algorithm/ . 下图用于测试：
a和b
a和c
b和a
b和c
c和d
d a公司
作为输出，我得到以下结果：设置0:[c，b，a，d]
我的问题是我需要所有的循环，所以我缺少了这个结果中的集合[a，b]和[a，c，d]。您现在知道是否有一种方法可以修改实现以获得所有周期吗？或者这个问题还有其他算法吗？
谢谢您！
1条答案
按热度按时间5us2dqdw1#
tarjan的算法不能找到所有的循环。它发现所有强连接的组件，这是不一样的事情。在一般情况下，不可能有效地找到所有的循环（对于一个完整的图，输出的大小是指数的）。此外，仅仅找到最长的循环已经是np困难的）。当然，你可以使用回溯法。