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
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:
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
- 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
- float getNodeX(ind index) - returns a speficified node's X
- float getNodeY(ind index) - returns a speficified node's Y
- 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
- 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
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