1

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

Svante
  • 50,694
  • 11
  • 78
  • 122
Programmer
  • 6,565
  • 25
  • 78
  • 125

2 Answers2

6

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.

salezica
  • 74,081
  • 25
  • 105
  • 166
  • for undirected graphs, to test if a cycle exists, i think ur solution is incorrect. consider : o----o – Programmer Dec 16 '10 at 19:25
  • You mean K2? I don't see the problem =S – salezica Dec 16 '10 at 19:26
  • Regarding your method to detect cycles in undirected graph, consider 2----1. If I start BFS from 1 I will begin by marking it as visited and add it to the queue. Then, in the while loop, I will retrieve it from the queue and mark any adjacent unvisited vertices as visited and add them to the queue. in other words, I will add 2 to the queue. Now, when I retrieve 2 from the queue, I will again consider all its adjacent vertices. In doing so, I will also consider 1 which is already visited. However, this does not indicate a cycle. – Programmer Dec 17 '10 at 07:11
  • 2
    The BFS algorithm doesn't work that way man. You don't re-use arcs, or it would always end in an infinite loop, regardless of what you're doing with your BFS. – salezica Dec 17 '10 at 13:32
  • I think you did not understand what I was saying. What do you mean by this statement: " aborts and reports a cycle found when it reaches a node previously marked as visited". In any version of BFS you may implement, there is a high chance that the BFS search will reach a node prviously marked as visited. Its just that we ignore this node and do not add it to the queue. Please clarify what you mean by "reaches"; – Programmer Dec 18 '10 at 07:48
0

You probably meant DFS, which is far more common in cycle detection, so I'll assume you made that mistake. Changing to BFS is fairly easy though as the core idea remains the same.

func detectCycle()
  for node in graph:
    visited = bool[N]
    set all visited to false
    detectCycle(n, n, visited)

func detectCycle(n, origin, visited)
  for neighbour in graph[n]
    if neighbour == origin
       cycle detected
    if not visited[neighbour]
       visited[neighbour] = true
       detectCycle(neighbour, visited)
       visited[neighbour] = false
moinudin
  • 134,091
  • 45
  • 190
  • 216