Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
While technically you could use either BFS or DFS, predominantly, DFS is used to find cycles in graphs.
DFS is more memory efficient than BFS as you can backtrack sooner, and it's also easier to implement. Once DFS finds a cycle, the stack will contain the nodes forming the cycle. The same is not true for BFS, so you need to do extra work if you want to print the cycle that was found.
Another characteristic to take into account is if the graph is directed or undirected. If you're dealing with a directed graph, 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. With a DFS you can mark nodes as you descend and unmark them as you backtrack.
In non directed graph with N nodes, if there are more than N-1 edges then it must have cycles. So all we need to do is find the number of edges and if they are equal or more than number of nodes then a cycle exists.
If we are dealing with undirected graphs there is a solution with O(V) complexity, we need to check that the graph is a forest, otherwise it will have cycle.
For a Directed Graph a simple DFS would reveal a cycle if we found a back node during the execution. The complexity would by O(V + E).
use depth first search or breadth first search. Complexity, time = O(E + V), space = O(V)
- as09 February 09, 2013