algorithm - Donald B. Johnson 的算法如何在有限的循环长度下工作？

Question

我了解到 Donald B. Johnson 于 1975 年发表的算法是一种在有向图中查找所有循环的有效方法。但是现在我有一个非常大的图表，但只需要找到长度有限的循环。如何修改它来做到这一点？

标签： algorithmgraph

Answer 1

首先，使用 dfs 可能更容易实现（仍然需要练习）。
其次，在计算强连通分量时，可以考虑计算与 startnode 的距离小于限制长度的所有节点，但这可能会增加时间复杂度。
最后，你可以利用多线程或并行计算，希望你能在 CodeCraft2020 中杀入决赛。