伪code。使用广度优先搜索来查找图形周期 [英] Pseudocode to find cycles in a graph using breadth first search

问题描述

请给我假code使用BFS寻找周期。我知道这种类型的其他问题存在，但没有给出code。

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.

至于伪code，那么，在一个无向图，这是一个传统的BFS的中止并报告发现了一个周期，当它到达一个节点previously标记为已访问。你可以找到伪$ C $下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周期是复杂得多两者在实际算法复杂和code复杂性方面。这就是为什么你不觉得假code。

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.

这篇关于伪code。使用广度优先搜索来查找图形周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！