CODEWITHSUNDEEP
algorithmsearchgraph-theorybreadth-first-search
Zephyr
Zephyr

Reputation: 1621

Detecting cycles using BFS

I know that this is a common question. But in many places I have read that cycle detection using BFS is not possible for directed graphs. One example is this link Why DFS and not BFS for finding cycle in graphs

I think that we can implement topological sort using BFS for a directed graph. If a topological order exists, then we can say graph is acyclic else it is cyclic. Is it not possible?

Upvotes: 2

Views: 2238

Answers (2)

Amit Sarker
Amit Sarker

Reputation: 36

It is possible to detect cycles with BFS! You can even detect the shortest cycle of a graph.

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

Omayowfade
Omayowfade

Reputation: 21

It is possible to detect cycles in a graph using a breadth-first algorithm approach, processing values through a queue. When you visit a vertex V, if any vertex U connected to V has already been visited and is NOT a parent of V, then a cycle exists in the graph. Otherwise, the graph has no cycle. This way is based on the assumption that no parallel edges are in the graph.

Upvotes: 2

Related Questions