我有数千个节点到数百万个节点的图表。我想检测这些图中所有可能的循环。
我使用哈希表来存储边缘。（（源节点，边权重）->（目标节点））。
在 OCaml 中实现它的有效方法是什么？
看起来 Tarjan 的算法是最好的算法。
什么可以是最多的实现。
问问题
948 次
2 回答
2
是的，Tarjan 的强连通分量算法是一个很好的解决方案。你也可以使用所谓的基于路径的强组件算法，它具有（如果仔细完成）相当的线性复杂度。
如果您选择合理的数据结构，它们应该可以工作。在您实施和分析原型实施之前，很难说更多。
我不明白你的图形表示是什么：你真的是一(node,weight)对散列键吗？那么如何找到给定节点的所有邻居呢？对于大型图结构，您当然应该优化访问时间，还要优化内存效率。
于 2012-06-24T14:43:34.883 回答
1
如果您真的想找到所有可能的循环，那么在最坏的情况下，问题似乎至少是指数级的。对于完整的图，每个非空节点子集都会为您提供不同的循环（包括从最后一个返回到第一个的链接）。此外，每个子集的每个循环排列都会给你一个不同的循环。根据您的图表的稀疏性，该问题在实践中可能是易于处理的。
于 2012-06-24T14:59:53.683 回答