java Tarjan的周期检测：缺少周期

Question

我已经用http://learn.yancyparedes.net/2012/03/strongly-connected-components-using-tarjans-algorithm/的实现试用了Tarjan的循环检测算法。 下图用于测试：
a b
a c
b a
b c
cd
d a
作为输出，我得到以下结果：Set 0:[c，b，a，d]

我的问题是我需要所有的循环，所以我缺少这个结果中的集合[a，b]和[a，c，d]。 您现在是否知道是否有办法修改实现以获得所有周期？或者这个问题存在另一种算法

谢谢大家!

Answer 1

Tarjan的算法不能找到所有的循环。它查找所有强连接的组件，这不是同一件事。在一般情况下，不可能有效地找到所有的循环（对于一个完整的图，输出的大小是指数的。而且，仅仅找到最长的循环已经是NP困难的）。当然，您可以使用回溯