BFS vs DFS

Note#150

notes
Published

2024-04-24

Source: https://py.mit.edu/spring24/readings/graph_search#_summary_of_bfs_vs_dfs

BFS

  • To implement a breadth-first search, we add and remove elements from opposite sides of the agenda. This approach is known as “first-in, first-out” (commonly written/pronounced as “FIFO”) since the element we remove is always the one that was added first.
  • BFS is guaranteed to return a shortest path to a goal vertex if such a path exists, regardless of the structure of our graph. Because we consider all paths of length n before considering any paths of length n + 1, we know that, when we first encounter a state that satisfies our goal condition, the path we’re considering must be optimal (in the sense that there is no shorter path to the goal).
  • BFS can run forever if it is being applied to an infinite graph with no solution, but it will always terminate in a finite graph or in an infinite graph where a solution exists.

DFS

  • To implement a depth-first search, we add and remove elements from the same side of the agenda. This approach is known as “last-in, first-out” (commonly written/pronounced as “LIFO”) since the element we remove is always the last one that was added.
  • DFS is guaranteed to find a path to the goal (but not necessarily an optimal one) if such a path exists and if the graph is finite.
  • DFS may run forever on an infinite graph, even if a solution exists.

DFS = Bad?

In all of the examples we have seen so far, DFS gives us a pretty gnarly path in the end, something that is kind of ugly and far from optimal. And, in the section above, we’ve stated that the guarantees that DFS offers us are weaker than those that BFS offers us. So, at this point, you may be thinking: why did we even bother introducing DFS? When would you ever want to use it?

The answer is a little bit nuanced, but the short version is that DFS tends to use less memory than BFS. If we consider a graph with a “branching factor” of b (i.e., every state is connected to b other states), then there will be around b^n paths of length n. This means that there will be around b^elements in the agenda when we’re considering the last path of length n − 1. By contrast, the agenda for a DFS will have around b × n elements in the agenda when considering a path of length n; and, as b and n increase, b × n is substantially smaller than b^n. This is especially useful in cases where we don’t care about finding the optimal path to a state (sometimes any path will do, or sometimes we’re just looking for a particular state and don’t care about the path at all); and, in those cases, DFS can sometimes be the right choice.