Which Procedure we can use for Maze exploration BFS or DFS

Question

I know we can use DFS for maze exploration. But I think we can also use BFS for maze exploration. I'm little bit confused here because most of the books and articles that I've read had used DFS for this problem. What I think is that the Best Case time complexity of DFS will be better as compared to BFS. But Average and Worst Case time complexity will be same for both BFS & DFS and thats why we prefer DFS over BFS. Am I right or I'm having some misconception

Solution 1

They have similar running time, but either may greatly outperform the other on any given problem simply due to the order in which the cells are visited.

In terms of space usage, BFS will on average use more memory for trees, but for more general graphs, in certain cases, it could use significantly less memory.

For mazes specifically (if we define a maze as there being only one way to reach a cell from the starting point without backtracking, meaning it's essentially a tree), BFS will generally use more memory, as we'll need to keep multiple paths in memory at the same time, where DFS only needs to keep track of a single path at any given time.

For more general grids, it's much less obvious which one will be better in terms of memory, especially when considering how we keep track of cells we've visited thus far to prevent repeatedly visiting cells.

If you're not concerned about memory, you can pick either. If you're fairly comfortable with recursion, DFS should be easier to implement.

However, if you're looking for the shortest path to some given cell in a general grid, use BFS (or A*), as that guarantees to find the shortest path, where DFS does not (you can still use either in a maze where there's only a single path to any given cell).

Solution 2

I'm quite amazed that nobody has mentioned so far about the difference in results given by DFS and BFS.

The main difference between these two algorithms is that BFS returns the shortest path and DFS returns just a path.

So if you want to get the shortest path use BFS, otherwise consider other pros and cons (memory etc.)

Solution 3

Both should be equivalent. DFS is used more because it is a bit easier to implement.

Comments

[Abhishek Bansal]

A DFS is perhaps easier to visualize for solving maze problems but performance-wise IMO both should be equivalent. One approach would fare better than the other depending on the case.

[artur grzesiak]

-1 bit easier to implement? DFS uses stack whereas BFS uses queue.

[yasen]

Isn't it? I can write DFS for a maze in 4-5 lines, one condition and 4 recursive calls. For BFS i would need in addition another loop as well as some lines for queue management.

[BlueRaja - Danny Pflughoeft]

-1 BFS is used way more often, because when there are multiple solutions it can return the shortest one, which is usually what we're interested in. DFS might not.

[yasen]

It is used more often if you know that the exit is somewhere near you, which is a completely different task. Otherwise, you would implement it in the easiest way. Moreover, dfs is more natural when it comes to maze traversal - a human will act in exactly the same way.