Which Procedure we can use for Maze exploration BFS or DFS

algorithm time-complexity depth-first-search breadth-first-search maze
Atinesh picture Atinesh · Nov 25, 2013 · Viewed 9.6k times · Source

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

Answer

pkacprzak picture pkacprzak · Nov 26, 2013

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

Related questions

Is the runtime of BFS and DFS on a binary tree O(N)?

I realize that runtime of BFS and DFS on a generic graph is O(n+m), where n is number of nodes and m is number of edges, and this is because for each node its adjacency list must be …

Read More
Time complexity of depth-first graph algorithm

I am starting to learn time complexity, and I looked in the examples for the time complexity for some simple sort. I wanted to know how do we calculate average time complexity for a depth-first search in a graph with |…

Read More
Time/Space Complexity of Depth First Search

I've looked at various other StackOverflow answer's and they all are different to what my lecturer has written in his slides. Depth First Search has a time complexity of O(b^m), where b is the maximum branching factor of …

Read More