Depth First Search in Java

#java

Elliot Forbes ⏰ 3 Minutes 📅 Apr 15, 2017

Depth First Search

DFS is another uninformed graph traversal algorithm which produces a non-optimal solution but can be useful for traversing quickly into deeper search domains. Depth first search is very similar to the previously covered breadth first search that we covered in this tutorial: breadth first search in Java

How it Works

With Depth first search you start at the top most node in a tree and then follow the left most branch until there exists no more leafs in that branch. At that point you will search the nearest ancestor with unexplored nodes until such time as you find the goal node.

If we take this binary tree as an example, the depth first search algorithm would do the following:

Add Node 1 to the stack
If Node 1 isn't the goal node then add Node 2 to the stack
Check if Node 2 is the goal node and if not add Node 4 to the stack.
If Node 4 isn't the goal node then add Node 8 to the stack.
If node 8 isn't the goal node then go to the nearest ancestor with unexplored children.
This happens to be Node 4, so we add Node 9 to the stack and check that.
If this isn't the goal node then we travel to Node 2 and explore it's unexplored children, Node 5.
and so on...

We continue to go down the left most nodes until we find the first path that reaches our goal node.

AbstractSearch Class

As a means of clearing up the code from all these tutorials I am going to add in an abstract class to which all of our graph traversal classes will extend and adhere to. The source code for this looks like so:

/**
 * AbstractSearch class so that we have a template
 * that all future graph traversal algorithms must adhere to.
 * this will make it far easier to "hot-swap" different algorithms
 * out for testing later on.
 */
public abstract class AbstractSearch {

    Node startNode;
    Node goalNode;

    public AbstractSearch(Node startNode, Node goalNode){
        this.startNode = startNode;
        this.goalNode = goalNode;
    }

    public abstract boolean execute();

}

Depth First Search Implementation

import java.util.ArrayList;
import java.util.Stack;

/**
 * depth first search implementation using a stack structure instead of a queue
 * structure as exhibited in the breadth first search algorithm
 */
public class DepthFirstSearch extends AbstractSearch{

    Node startNode;
    Node goalNode;

    public DepthFirstSearch(Node start, Node goalNode){
        super(start, goalNode);
        this.startNode = start;
        this.goalNode = goalNode;
    }

    public boolean execute(){
        if(this.startNode.equals(goalNode)){
            System.out.println("Goal Node Found at 0 depth");
            System.out.println(startNode);
        }
        Stack<node> nodeStack = new Stack<>();
        ArrayList<node> visitedNodes = new ArrayList<>();

        nodeStack.add(startNode);

        while(!nodeStack.isEmpty()){
            Node current = nodeStack.pop();
            if(current.equals(goalNode)){
                System.out.print(visitedNodes);
                System.out.println("Goal node found");
                return true;
            }
            else {
                visitedNodes.add(current);
                nodeStack.addAll(current.getChildren());
            }
        }
        return false;
    }

}

Updating our Driver class

Due to the fact we've created an abstract search class we can now do something similar to this in our driver class:

/**
 * Created by elliotforbes on 24/06/15.
 */
public class Driver {

    public static void main(String args[]){
        Node station1 = new Node("Westminster", null, null);
        Node station2 = new Node("Waterloo", station1, null);
        Node station3 = new Node("Trafalgar Square", station1, station2);
        Node station4 = new Node("Canary Wharf", station2, station3);
        Node station5 = new Node("London Bridge", station4, station3);
        Node station6 = new Node("Tottenham Court Road", station5, station4);

        // We instantiate searchAlgo as type AbstractSearch but we set it to equal
        // our newly created DepthFirstSearch concrete class implementation
        AbstractSearch searchAlgo = new DepthFirstSearch(station6, station1);

        if(searchAlgo.execute())
            System.out.print("Path Found!");
    }
}

Depth First Search in Java