Solution for Which is better DFS or BFS? [closed]
is Given Below:
If a particular task can be achieved by using any of DFS or BFS, then which one should I choose
to get the task done in minimum time and space (I am not talking about complexities coz it is the same for both approaches. I am talking about actual approx time and space required for execution)?
I’ll start with saying that DFS and BFS have different applications. There are problems that can be solved both with DFS and BFS and in general they’re performing equally. As said in the comments, performance and memory usage heavily depends on the topology of the graph, some cases are considered in this answer https://stackoverflow.com/a/3332994/4655217. I’m saying generally to refer graphs with evenly distributed relations.
Stack as its storage, it has
O(1) access time and
O(1) push time. While BFS uses
Queue, which has the same asymptotic complexity, moreover it requires approximately the same number of operations for pop and push while using the most common implementation based on arrays. Both for
Queue based on array, to add element to our container we need to add element to the end of array and increment counter. To pop from
Stack we’re decrementing counter, to pop from
Queue, we’re incrementing front pointer. Nothing which may result in significant performance differences.
Queue require the same amount of memory when implemented using an array, so there is completely no difference between these algorithms.
There is a possibility to implement DFS using recursion, which requires less code to implement, but this implementation may consume more memory and may fail on big graphs causing stack overflow. By contrast, BFS can’t be implemented using recursion. So, DFS may be easier to implement using recursion, but when using iterative approach, basic implementations differ only in container choice (
They’re the same when you need to accomplish something achievable by both DFS and BFS, e.g. iterate over all vertices of a graph.