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

Question

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

Answer 1

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

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

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

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