java - Tarjan 的循环检测：缺少循环

Question

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

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

谢谢！

Answer 1

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