CODEWITHSUNDEEP
algorithmgraphbreadth-first-search
Serra Cordova
Serra Cordova

Reputation: 21

Cycle detection with BFS

I am trying to detect cycles with BFS algoritm in a directed graph. My main idea to detect the cycles is: since BFS visites each node (and edge) only once, if I encounter an already visited node again; it causes a cycle. However, my code sometimes finds the cycle, sometimes not.

The pseudo code I modified from Wikipedia is below:

1  procedure BFS(G,v):
2      create a queue Q
3      enqueue v onto Q
4      mark v
5      while Q is not empty:
6          t <- Q.dequeue()
7          if t is what we are looking for:
8              return t
9          for all edges e in G.adjacentEdges(t) do
12             u <- G.adjacentVertex(t,e)
13             if u is not marked:
14                  mark u
15                  enqueue u onto Q
16             else:
17                  print "Cycle detected!" //since we saw this node before

What am I missing?

Upvotes: 2

Views: 2756

Answers (4)

Amit Sarker
Amit Sarker

Reputation: 36

Your algorithm will not always find cycles. Because, if the node v is not present in any cycle or it is not possible to reach a cycle from node v then it won't work. We can do some modifications. The number of nodes equals to n. Run a bfs from each node. Pseudocode:

1 create a queue Q
2 create a array visited
3 create a array level
4 set answer = infinity
5 for each node 1 to **n**
6      mark the visited equals to **0**.  
7      clear the **Q**
8      enqueue **v** onto Q
9      visited [ v ] = 1
10     while Q is not empty:
11            t <- Q.dequeue()
12            for all edges e in G.adjacentEdges(t) do
13            u <- G.adjacentVertex(t,e)          
14            if u is not visited:
15                 visited [ u ] = 1
16                 level [ u ] = level [ t ] + 1;
17                 enqueue u onto Q
18            else:
19                 answer = min( answer , level [ t ] + level [ u ] + 1 )

After finishing the algorithm you'll have the minimum cycle in the entire graph as the answer.

Upvotes: 0

Jatin
Jatin

Reputation: 14269

The algorithm you have given might report the existence of a cycle even if no cycle exists. In line number 12, you we have u adjacent to t. A parent of t in BFS tree also lies in it's adjacency list. So, line 13 might return false even when no cycle exist because a parent of t is marked and is a part of t's adjacency list.

So, I think this algorithm will report a cycle if it is present but it might also report a cycle even when there is none.

Upvotes: 0

Konsol Labapen
Konsol Labapen

Reputation: 2434

The problem with your implementation is that it assumes the graph is connected. But the reality is you may be deal with a graph that has two connected portion, so that if you start with v you will never get into the other portion. To solve your problem, you need to find a way to identify subgraphs that may not be connected. You may find some suggestions on wikipedia http://en.wikipedia.org/wiki/Topological_sorting#Algorithms where they talk about 

 S ← Set of all nodes with no incoming edges

EDIT:

actually an easy change you can make is instead of enqueueing v, enqueue all the nodes Dijkstra style. That way you should always find your cycle. Also where are you getting t from since it's not part of the method signature?

Upvotes: 0

Mattias Andersson
Mattias Andersson

Reputation: 2341

The algorithm you've given may find the target node (and therefore quit) before it finds the cycle.

Which is more important to you: finding the target as quickly as possible or finding the cycle? If you don't care at all about the target, you can remove that part of your algorithm.

Upvotes: 4

Related Questions