在有向图中找出所有的环路

Question

标题已经很明确了。这里是我在互联网上找到的一种解决方法，可以帮助做到这一点。这是链接。

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

此外，我不知道如何使用/不使用这个解决方法。

- Mathejunior

---

你为什么认为你需要这样做？ - Matt Timmermans

Answer 1

让我们将其限制为简单循环-那些不包含子循环的循环。对于图中的每个节点，开始一个深度优先搜索，以查找该节点。记录导致匹配的递归树的每个分支。在搜索过程中，永远不要越过已经遍历过的节点。

考虑具有n个顶点的完全有向图。有n(n-1)个弧和n!个长度为n的简单循环。以上算法并没有比这更糟糕。在最坏情况下，仅构造答案的新副本所需的时间几乎与运行上述算法所需的时间相同。

- Patrick87

Answer 2

如果你想在一个有向（或者无向）图中寻找循环，有一个直观的方法：

For each edge (u, v) in the graph
     1. Temporarily ignore the edge (u, v) in step 2
     2. Run an algorithm to find all paths from v to u (using a backtrackig algorithm)
     3. Output the computed paths in step 2 along with the edge (u, v) as cycles in the graph

请注意，这种方法会导致重复的循环结果出现，因为长度为 k 的循环将被发现 k 次。

你可以尝试运用这个想法去寻找具有特定属性的循环。例如，如果你的目标是在图中寻找最短的加权循环而不是找到所有的循环，你可以在第二步中使用 Dijkstra，并在找到的所有循环中取最小值。如果你想要找到边数最少的循环，你可以在第二步中使用 BFS。

如果你更困难的是在图中找到所有路径，这道题可能会对你有所帮助。虽然它与问题略有不同。

使用回溯算法计数/查找路径

- A. Mashreghi