.:: CODE SNIPPET ::.

"Your time is limited, so don't waste it living someone else's life"

Searching algorithm DFS


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.

The first use of this algorithm is when Theseus entered the Labyrinth to kill the monstrous Minotaur. Ariadne instructed Theseus to use a ball of string to find his way back out.

Implementation:

    /** The edge to. */
    private Integer[] edgeTo;

    /** The list steps. */
    private final List<Integer> lstSteps = new ArrayList<Integer>();

    /** The marked. */
    private boolean[] marked;

    /** The source. */
    private final int source;

    /**
     * Constructs a new <tt>DepthFirstPaths</tt>.
     *
     * @param graph the graph
     * @param source the source
     */
    public DepthFirstPaths(final Graph graph, int source)
    {
        this.graph = graph;
        this.marked = new boolean[graph.getNumOfVertices()];
        this.edgeTo = new Integer[graph.getNumOfVertices()];
    }

    /**
     * Dfse.
     *
     * @param graph the graph
     * @param vertex the vertex
     */
    private void dfs(final Graph graph, int vertex)
    {
        this.marked[vertex] = true;
        this.lstSteps.add(vertex);
        List<Vertex> adjacentVertices = graph.getAdjacentVerticesOf(vertex);
        int i = 0;
        while (i < adjacentVertices.size())
        {
            Vertex w = adjacentVertices.get(i);
            if (!this.marked[w.getValue()])
            {
                this.edgeTo[w.getValue()] = vertex;
                this.dfs(graph, w.getValue());
            }
            i++;
        }
        if (this.edgeTo[vertex] == null)
        {
            return;
        }
        else if (i >= adjacentVertices.size())
        {
            this.lstSteps.add(this.edgeTo[vertex]);
        }
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: