Archive

Posts Tagged ‘DFS’

Searching algorithm DFS

December 19, 2014 Leave a comment

Depth first search (DFS) is a searching algorithm used in searching maze.
Prerequisites:
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…

Advertisements
Categories: Algorithm, Java Tags: ,
%d bloggers like this: