December 19, 2014
Posted by on
Depth first search (DFS) is a searching algorithm used in searching maze.
A maze is also a graph with: a vertex equals a intersection, and edge is passage. (So, we should have some basic knowledge about graph, this will is be stored in some next posts)
The goal of using this algorithm in maze is explore all the connected intersections with a start point in the maze.
Algorithm for DFS:
+ Mark the visited intersection by a nut on the string.
+ Enter any passage related with that intersection that have never visit before and unroll the ball of string to mark that passage.
+ Retrace steps when no unvisited options.
Read more of this post