java - Tarjan 的循环检测 : missing cycles

Question

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

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

谢谢!

Answer 1

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