使用广度优先搜索在图中查找循环的伪代码 [英] Pseudocode to find cycles in a graph using breadth first search

问题描述

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

Please give me pseudocode for finding cycles using BFS. I know other questions of this type exist but NONE give the code.

推荐答案

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

Just in case, DFS is much more suitable for the task, even more so in directed graphs. If you already knew that, ignore this.

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

As for the pseudocode, well, in an undirected graph, it's a traditional BFS that aborts and reports a cycle found when it reaches a node previously marked as visited. You can find pseudocode for BFS here.

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

In a directed graph, it gets trickier, since you have to remember which way were you walking when you reached the node, and the spatial complexity disadvantage over DFS gets even worse.

哦，我说的是测试循环图，而不是真正找到循环.使用 DFS 查找循环几乎是微不足道的，而使用 BFS 查找循环在实际算法复杂性和代码复杂性方面要复杂得多.这就是为什么你找不到伪代码.

oh, I was talking about testing a graph for cycles, not actually finding the cycle. Finding cycles with DFS is close to trivial, while finding cycles with BFS is much more complex both in terms of actual algorithmic complexity and code complexity. That's why you don't find pseudo-code.

这篇关于使用广度优先搜索在图中查找循环的伪代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！