Menu
Predominantly DFS is used to find a cycle in graphs and not BFS. Any reasons? Both can find if a node has already been visited while traversing the tree/graph.
287
Steps involved in detecting cycle in a directed graph using BFS. Step-1: Compute in-degree (number of incoming edges) for each of the vertex present in the graph and initialize the count of visited nodes as 0. Step-3: Remove a vertex from the queue (Dequeue operation) and then. Increment count of visited nodes by 1.
Depth First Traversal can be used to detect a cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is joining a node to itself (self-loop) or one of its ancestor in the tree produced by DFS.
We do a BFS traversal of the given graph. For every visited vertex 'v', if there is an adjacent 'u' such that u is already visited and u is not a parent of v, then there is a cycle in the graph. If we don't find such an adjacent for any vertex, we say that there is no cycle.
DFS uses Stack to find the shortest path. BFS is better when target is closer to Source. DFS is better when target is far from source. As BFS considers all neighbour so it is not suitable for decision tree used in puzzle games.
Depth first search is more memory efficient than breadth first search as you can backtrack sooner. It is also easier to implement if you use the call stack but this relies on the longest path not overflowing the stack.
Also if your graph is directed then you have to not just remember if you have visited a node or not, but also how you got there. Otherwise you might think you have found a cycle but in reality all you have is two separate paths A->B but that doesn't mean there is a path B->A. For example, 
If you do BFS starting from 0, it will detect as cycle is present but actually there is no cycle.
With a depth first search you can mark nodes as visited as you descend and unmark them as you backtrack. See comments for a performance improvement on this algorithm.
For the best algorithm for detecting cycles in a directed graph you could look at Tarjan's algorithm.
195
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
