Graph traversal

Question

Why DFS is more efficient than BFS in determining the presence of a cycle in graph ?Explain please .

Comments

http://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs

Answer 1

DFS and BFS both detects cycle in directed and undirerected graphs in $O(V+E)$.

The reason for using DFS is that it is easier to implement using stack. With much efficient memory utilization, we can backtrack to find if a node has been visited more than once. Stack will contain the nodes forming cycle. With BFS, each vertex needs to be extracted from the queue if we want to print the cycle.

Comments

In DFS ,it has no guarentee that it will detect the cycle sometime it fails also . As example in control flow graph(CFG).