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)?
Asked
Active
Viewed 442 times
-2
-
Depends on the shape of your graph. (Obligatory: https://xkcd.com/761/) – Nate Eldredge Aug 02 '21 at 14:36
-
1Can you elaborate on "depends on your graph"? I think you mean "if there are linked list-like relations in the graph then BFS better than DFS right? But this is a special case. Let's say my graph have evenly distributed relations between the nodes and across the nodes. then? – lnx Aug 02 '21 at 14:48
1 Answers
3
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.
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.
geobreze
- 2,274
- 1
- 10
- 15