Menu

Learning Java

Articles
Author Profiles
Lessons
FAQ's
Books
Newsletter
Tutorials
Talk Java!

Using Java

Applets
JavaBeans
Servlets
Resources
Discuss Java

Looking for Java resources? Check out the Java Coffee Break directory!

Implementing Depth First Search

There are two active Java applets in this book that show a demonstration of depth first and breadth first search . These two Java applets show a simple network:

Before we design and implement any search programs, we will "walk through" a search of this simple network, trying to find a path from node "0" to node "9". Specifically, we will manually perform a depth first search.

Running the depth first search applet

Editor's note :  The source code for the applet is accessible here, and also relies on SearchApplet.java.

Depth first search applet

In the file DepthFirstSearch.java, we define the positions of nine test nodes:

        addNode("0", 0.0f, 0.0f);
        addNode("1", 1.0f, 1.0f);
        addNode("2", 5.0f, 2.0f);
        addNode("3", 2.0f, 5.0f);
        addNode("4", 7.0f, 5.0f);
        addNode("5", 8.0f, 8.0f);
        addNode("6", 10.0f, 5.0f);
        addNode("7", 8.0f, 2.0f);
        addNode("8", 12.0f, 8.0f);
        addNode("9", 13.0f, 5.0f);

In the above figure showing our sample network, we define the "links" in the following order:

        addLink(0,1);
        addLink(1,2);
        addLink(2,3);
        addLink(2,4);
        addLink(4,5);
        addLink(4,6);
        addLink(6,8);
        addLink(8,9);
        addLink(2,7);
        addLink(7,9);                

The order that the links are defined is important in a depth first search. if we start at node "0" and search to node "9", then we find the first link leaving node "0" (in this case link "0" to "1"). Then we take the first link leaving node "1" (in this case link "1' to "2"), etc. When we "run out of" links to explore from a given node, then we "back up" to the preceeding node, and explore all other links that leave that node.

I am sure that you have already tried running the depth first search applet, right? Then you will have noticed that it found a rather long path from node "0" to "node "9". The depth first search applet stops when it has found a path. The breadth first search applet in Chapter 6 finds better paths, in general. I assume that you know how to program in Java, so I will just briefly explain what each method in classes SearchApplet and DepthFirstSearch. We will discuss the implementation of BreadthFirstSearch in Chapter 6.

Methods in SearchApplet

• init - this method is called by the applet container (e.g., a Java enabled web browser, or the "appletviewer" utility) when an applet is started. Here, we just get the applet width and height, and set up two Java AWT "Choice" controls so that the user of the applet can change the start and goal nodes. We use internal anonymous classes to handle events for the "Choice" controls, so this applet requires Java version 1.1 or higher.
• repaintPath(int [] path, int num_in_path) - this is a graphics utility method for drawing a specified path on the applet's canvas.
• repaintPath(int [] path) - this is a graphics utility method for drawing a specified path on the applet's canvas.
• paintNode(Graphics g, String name, int x, int y) - this is a simple utility method for drawing a node at a specified location.
• paint(Graphics g) - this method is called by the applet's container whenever the applet needs to update its display.
• addNode(String name, float x, float y) - for adding a new node to the network.
• String getNodeName(int index) - returns a specified node's name.
• float getNodeX(ind index) - returns a speficified node's X coordinate.
• float getNodeY(ind index) - returns a speficified node's Y coordinate.
• float getPathLength(int index) - returns a specified link's length. This is not currently used, but would be required for adding heuristics to the search.
• addLink(int index1, int index2) - for adding a link given two node indices.
• addLink(String name1, String name2) - for adding a link given two node names.
• abstract int [] findPath(int node_1, int node_2) - this is an abstract method for finding a path between two specified nodes. This method will be overriden in the classes DepthFirstSearch and BreadthFirstSearch
• int getNodeIndex(String node_name) - returns the node index, given its name.

Methods defined in class DepthFirstSearch

The class DepthFirstSearch is derived from the class SearchApplet and defines the following methods:

• init - this method defines a test network, then calls the super class SearchApplet method init.
•  
• int [] findPath(int node_1, int node_2) - this is a method for finding a path between two specified nodes using a depth first search as described in the text. The return value for this method is an array of node indices.
• int [] findPathHelper(int [] path, int num_path, int goal_node) - this is the actual search method that calls itself recursively.
• repaintPath(int [] path, int num_path) - converts an ordered list of node indices to a doubled up list, then calls the super class method repaintPath.
• int [] connected_nodes(int [] path, int num_path) - this is a helper method called by findPathHelper that finds all nodes connected to the last node on the current path that are not already on the current path.

int [] copy_path(int [] path, int num_to_copy) - this is a helper method called by findPathHelper that copies a path array.

If you have not already done so, return to the table of contents page, and experiment with the depth first search applet.

Next : Implementing Breadth First Search

Back to main