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 Breadth First Search

We saw in Chapter 5 how networks are initialized in the base class SearchApplet and the implementation of the derived class DepthFirstSearch. In this chapter, we will derive another class BreadthFirstSearch from class SearchApplet that calculates, in general, better paths that the depth first version. You can use this new class in your own applications, optionally adding search heuristics for the particular type of problem that you are solving.

Running the depth first search applet

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

Breadth first search

The breadth first search uses a Queue data structure (a queue is a sequence that is "first in, first out"; that is, you remove items from a queue in the same order that they were added). If we want to perform a breadth first search from node "0" to node "9", we start by putting all of the nodes connected to node "0" on the queue. Then we add the nodes connected to the items currently in the queue, and continue this process until we arrive at the goal node.

For many applications, you would want to add heuristics to a breadth first search by controlling the "order in which nodes are added to the queue. For example, let us look again at our sample network:

If we are starting at node "4" and searching for node "9", then we would first add the following nodes to the queue:

• 2
• 5
• 6

The BreadthFirstSearch class adds these nodes in an arbitrary order. However, you might want to add (this is an exercise for the reader) the heuristic that you add nodes that are closer to the goal node first. For most problems, the ordering of nodes added to the queue will have a dramatic effect on performance. If we ordered the nodes connected to node "4" in order of closeness to the goal node "9", then we would add them in this order:

• 6
• 5
• 2

Methods defined in class BreadthFirstSearch

The class BreadthFirstSearch 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 breadth first search as described in the text. The return value for this method is an array of node indices.
• Inner class Queue - this utility class implements a standard Queue data structure, and is used by method findPath.
• int [] connected_nodes(int node) - this is a helper method called by findPath that finds all nodes connected to a specified node.

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

This concludes my "book" on simple search techniques in Java. Really, I have just skimmed the surface of this material, but I hope that reading this book has provided you with both some understanding of search techniques, and some Open Source Java source code that you can use for both education and in your own software products.

Next : Source code listings

Back to main