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://codeutlity.org/a/3332994/4655217. I’m saying *generally* to refer graphs with evenly distributed relations.

## Performance

DFS uses `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 `Stack`

and `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.

## Memory usage

Both `Stack`

and `Queue`

require the same amount of memory when implemented using an array, so there is completely no difference between these algorithms.

## Programmer’s POV

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 (`Stack`

or `Queue`

).

## Summary

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.