CODEWITHSUNDEEP
algorithmdata-structuresgraph
Programmer
Programmer

Reputation: 6753

Pseudocode to find cycles in a graph using breadth first search

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

Upvotes: 1

Views: 22326

Answers (2)

moinudin
moinudin

Reputation: 138477

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

Upvotes: 0

salezica
salezica

Reputation: 77089

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.

Upvotes: 6

Related Questions