algorithm - 使用广度优先搜索在图中查找循环的伪代码

Question

请给我使用 BFS 查找循环的伪代码。我知道存在其他此类问题，但没有给出代码。

Answer 1

以防万一，DFS 更适合这项任务，在有向图中更是如此。如果您已经知道这一点，请忽略它。

至于伪代码，好吧，在无向图中，它是一个传统的 BFS，当它到达先前标记为已访问的节点时，它会中止并报告发现的循环。您可以找到 BFS 的伪代码 here .

在有向图中，它变得更加棘手，因为您必须记住到达节点时您走的是哪条路，并且 DFS 的空间复杂性劣势变得更糟。

编辑:哦，我说的是测试循环图，而不是实际找到循环。使用 DFS 查找循环几乎是微不足道的，而使用 BFS 查找循环在实际算法复杂性和代码复杂性方面要复杂得多。这就是您找不到伪代码的原因。