algorithm - 在有向图中查找所有循环路径

Question

标题是不言自明的。这是我在互联网上找到的一个解决方案，可以帮助做到这一点。这是链接

我不明白为什么不访问权重低于给定阈值的顶点会解决问题。

另外，我不知道如何使用/不使用它来解决这个问题。

标签： algorithmgraph-algorithm

Answer 1

让我们将其限制为简单的循环——那些不包含子循环的循环。对于图中的每个节点，开始对该节点进行深度优先搜索。记录导致匹配的递归树的每个分支。搜索时，切勿越过已在分支中遍历的节点。

考虑 n 个顶点上的完整有向图。有 n(n-1) 条弧和 n! 长度为 n 的简单循环。上面的算法一点也不比这差多少。至少在最坏的情况下，简单地构建答案的新副本将花费几乎与运行上述算法一样多的时间。