2

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?

Dominique Fortin
  • 2,212
  • 15
  • 20
Zephyr
  • 1,521
  • 3
  • 22
  • 42
  • I think this question would be better answered on https://cs.stackexchange.com/ – Derek Brown Nov 17 '17 at 17:34
  • @DerekBrown I think that it is a simple algorithm question which can be answered here. – Zephyr Nov 17 '17 at 17:38
  • StackOverflow tends to be more about pragmatic problems rather than theoretical ones. Your question is "is it possible?"- which falls more in the realm of CS versus StackOverflow- we tend to require some code (at least pseudocode). You can learn more about this distinction https://meta.stackexchange.com/questions/129598/which-computer-science-programming-stack-exchange-do-i-post-in – Derek Brown Nov 17 '17 at 17:42
  • Of course you can use BFS to determine if there's a cycle in a directed graph. Doing so is not terribly efficient, though, for the reasons described in multiple answers to your linked question. – Jim Mischel Nov 17 '17 at 17:44
  • Probable duplicate of https://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs. – Jim Mischel Nov 17 '17 at 17:44
  • The `algorithms` tag is for just this sort of question. However, the issue is answered well enough in the OP's linked question. The responses that state it's impossible with BFS are simply wrong. BFSA, in general, wcan solve the problem; it's just that the canonical, undirected BFS algorithms don't adapt immediately to directed graphs. – Prune Nov 17 '17 at 17:47
  • 2
    Possible duplicate of [Why DFS and not BFS for finding cycle in graphs](https://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs) – Prune Nov 17 '17 at 17:47
  • @JimMischel Why BFS is not efficient? Topological sort using BFS can be found in O(V+E) time which is same as DFS when used to find cycles. – Zephyr Nov 17 '17 at 17:56
  • @Prune I already gave the link to the same question in the post. – Zephyr Nov 17 '17 at 17:58
  • 1
    @Zephyr Yes, I mentioned that in my comment. The responses obviate the premise of your question. Yes, topological sort works just fine. – Prune Nov 17 '17 at 18:06
  • @Zephyr why you want to use BFS when it takes 2x more memory then dfs? Where do you see the problem in dfs? – Luai Ghunim Nov 17 '17 at 18:56

2 Answers2

2

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.

Hyu
  • 31
  • 3
Omayowfade
  • 21
  • 2
0

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.

Amit Sarker
  • 36
  • 5