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

Caughey

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. – Murmurous

Use DFS because it is easier to implement & reconstruction of solution is easy. – Pelican

Answer 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).

Johnnyjumpup

For an complex maze, DFS saves more memory than BFS on average. Consider a search tree with m tiers and each parent node having b child nodes. The largest momery DFS will take is O(bm) while it is O(b^m) for BFS. – Brittaneybrittani

Answer 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.)

Mannes

Answer 3

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

Place

bit easier to implement? DFS uses stack whereas BFS uses queue. – Chucklehead

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. – Place

@arturgrzesiak: Stack-based algorithms are generally easier to implement because the stack can be implicit (leveraging the call stack of the recursive algorithm) rather than explicit (requiring a "wrapper" function that creates a queue and a "helper" function that receives that queue as a by-reference parameter). So while it's nominally a stack/queue tradeoff, programming languages are generally better set up to handle DFS traversals than BFS. – Fokker

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. – Kunkel

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. – Place

Answer 4

BFS take too much memory, its not good for huge maze.

Carnatic