algorithm - Pseudocode to find cycles in a graph using breadth first search

Question

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

Answer 1

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

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.

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.

Edit: 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.