列出一个非常大的有向图中的所有循环

Question

我想问的是，是否有可能在一个非常大的有向图中列出所有的循环。图的大小约为600个节点和7000条边。你知道吗

我尝试过朴素的dfs算法，并使用python进程实现了多线程。我将其设置为使用10个进程。问题是，我仍然不能完成程序。时间太长了。我注意到它列出了许多重复的周期。例如，我发现一个循环由200个节点组成。这意味着它计算同一个周期200*200次！我相信它是无用的，因为它是一个循环。你知道吗

我尝试过约翰逊算法，但我的64GB内存不能处理它。它说内存用完了。你知道吗

我所做的其他事情是列出一个循环是否存在于两个节点之间。你知道吗

我检测节点A是否可以到达节点C，节点C是否可以到达节点A，这意味着至少有一个循环涉及到A和C。这个算法非常快，我可以列出大约600000种可能性，尽管我知道也有很多重复。例如，如果A可以到达B，B可以到达C，C可以到达A，这意味着A和C以及B和C之间有一个循环

我该怎么办？你知道吗

Answer 1

当然，会有完美的算法来解决您的问题，但是您可以通过找到图中的强连通组件来删减一些处理。SCC的节点不可能与另一SCC的节点形成循环。因此，您可以分别为不同的scc运行当前算法，这样可以节省大量的处理和遍历。你知道吗