Why DFS and not BFS for finding cycle in graphs

by

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.

More Related Contents:

  1. What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
  2. Find all paths between two graph nodes
  3. Breadth First Vs Depth First
  4. Why is the time complexity of both DFS and BFS O( V + E )
  5. Why is depth-first search claimed to be space efficient?
  6. Best algorithm for detecting cycles in a directed graph [closed]
  7. Finding all cycles in a directed graph
  8. Cycles in an Undirected Graph
  9. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  10. Non-recursive depth first search algorithm [closed]
  11. Find the shortest path in a graph which visits certain nodes
  12. Compute the minimal number of swaps to order a sequence
  13. What is the difference between tree depth and height?
  14. Performing Breadth First Search recursively
  15. Find the paths between two given nodes?
  16. Finding all the shortest paths between two nodes in unweighted undirected graph
  17. How to implement depth first search for graph with a non-recursive approach
  18. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  19. Iterating over a Binary Tree with O(1) Auxiliary Space
  20. Hashing a Tree Structure
  21. reconstructing a tree from its preorder and postorder lists
  22. What are the differences between segment trees, interval trees, binary indexed trees and range trees?
  23. Algorithm to simplify a weighted directed graph of debts
  24. Print the biggest K elements in a given heap in O(K*log(K))?
  25. Number of paths between two nodes in a DAG
  26. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  27. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  28. Iterative tree walking
  29. Finding connected components of adjacency matrix graph
  30. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1

Leave a Comment