CODEWITHSUNDEEP
cdepth-first-searchmaze
Krzysiek
Krzysiek

Reputation: 1527

open maze - Depth First Search

I have an open maze with a start point and an endpoint. I wrote a BFS and a DFS search algorithm to solve the maze. My BFS finds the shortest solution, but my DFS (which goes down, left, up, right) creates a zigzag as a solution. Is this correct? How should DFS behave in an open maze?

edit: http://postimg.org/image/n049oua8n/ here is the path, starting form P. The endpoint is on the bottom, but the mid-path looks wrong to me =/ I think the algorithm is skipping a column, right? it should fill the middle section completely?

Upvotes: 2

Views: 1382

Answers (2)

pNre
pNre

Reputation: 5376

Yes, it correct because DFS explores the graph in depth (and doesn't find the shortest paths). Given the source of a visit s, DFS visits one of its neighbors u, then one of u's neighbors going in depth. When all the neighbors of a given node are visited another neighbor of the parent node is visited, and so on.

DFS

While BFS, given the source of the visit s first visits all it's neighbors and then begins deepening.

BFS

Upvotes: 2

Joni
Joni

Reputation: 111329

That sounds correct: a DFS will go as deep in the maze as it can in the first direction (down), and when it can't get any further it will backtrack to the last crossroads and go left, and then down again.

There is a painting algorithm called "flood fill" which fills a space with color by making a DFS or BFS of the pixels. The animations of its working give a nice graphical representation of the differences between the two graph search algorithms.

This is a food fill with BFS, as you can see it searches the space in every direction:

Flood fill with BFS

This is a flood fill with DFS, as you can see it searches the space first in one direction, and then backtracks to fill holes:

enter image description here

Upvotes: 1

Related Questions