Depth First and Breadth First Search - Page 5

On the previous page, you learned how to implement our two search algorithms in pseudocode and ActionScript. In this page, I will provide an explanation of what the code actually does.

Because both depth first and breadth first search methods contain the same data except for one line, I will not describe each method's code separately.

var origin:Node = nodeOrigin;

var destination:Node = nodeDestination;

In these two lines, you are defining and initializing your origin and destination variables. In order to keep the code example applicable to a wider set of Flash implementations, I am assuming your origin and target nodes are already somehow given to you and stored in the nodeOrigin and nodeDestination variables.

Your implementation of it, if you are using the Graph ADT will be different. In the next page, you will see in my implementation, nodeOrigin and nodeDestination are replaced with something else.

// Creating our Open and Closed Lists

var closedList:Array = new Array();

var openList:Array = new Array();

// Adding our starting point to Open List

openList.push(origin);

I declare our closedList and openList arrays. These arrays store the progress of what we have done so far and a list of what needs to be done.

For the initial step from our algorithm, I add the origin node to our openList. With that done, it's time to get into our loop!

// Loop while openList contains some data.

while (openList.length != 0) {

As long as our openList contains some data, we continue looping. Ideally, openList should always contain some data such as nodes from recently explored neighbors. If openList is empty, besides the loop ending, it also means that you have explored your entire search tree without finding a solution.

// Loop while openList contains some data.

var n:Node = Node(openList.shift());

An array's shift method removes the first item from the array and returns that value. Because I specify that the variable n requires an object of type Node, I typecast our openList.shift() operation with the Node(data) operation. If I did not do that, Flash would give me an error.

The main thing to remember for the rest of this code explanation is that the variable n refers to the current, active node removed from openList.

Thanks to TheCanadian for helping me out with the typecasting syntax.

// Check if node is Destination

if (n == destination) {

closedList.push(destination);

trace("Done!");

break;

}

I first check if n is our destination. If the current node you are examining is the destination, you are done. I add n to our closedList array and trace the string Done!.

If you are going to be parsing your data or making any modifications to your final output stored in closedList, you would do so right here before the break command.

// Store n's neighbors in array

var neighbors:Array = n.getNeighbors();

var nLength:Number = neighbors.length;

If your program makes it here, it means that n is not our intended destination. We now have to find out who its neighbors are. I use the getNeighbors method on n to return an array of its neighbors.

In order to simplify how future lines of code look, I store the length of our recent neighbors data in the nLength variable.

// Add each neighbor to the beginning of our openList

for (i=0; i< nLength; i++) {

< depends on search method >

}

This for loop cycles through each of our neighbors and adds the values to openList. The location at which the neighbors get added to our openList (grayed out line) is where the difference between depth first and breadth first searches occur.

The following two subsections explain what the grayed out code does in both our search methods:

Depth First Search
The gray code in a depth first search is replaced with the following:

openList.unshift(neighbors[nLength - i - 1]);

Unshift inserts values at the beginning of our array. Therefore, I add the values to the beginning of our array in reverse; hence the awkward syntax: nLength - i - 1. Let me give you an example.

Let's say my neighbors array contains the following three items: a, b, c. If I were to unshift each item using neighbors[i], in the first iteration of the for loop, the value of a will be added to the first position in our openList. So far so good.

In the second iteration, the value of b will be added to the first position in our openList. So now, openList contains b first, then a: [b, a]. In the third iteration, your openList will look like [c, b, a]. The end result is that the data is reversed!

To avoid the reversal, I add the items to our openList in reverse. First c gets inserted, then b, then a. That works in keeping with our algorithm and examples from the previous pages.

Breadth First Search
The gray code in a breadth first search is replaced with the following:

openList.push(neighbors[i]);

This is very straightforward. Push adds a value to the end of your array, and since that is what we need to do for breadth first search anyway, we are done...well, almost.

// Add current node to closedList

closedList.push(n);

Finally we are at the end. Since we have already done everything we can to this node (check if it is our destination and get its neighbors), let's retire it by adding it to our closedList array.

With the code explanation out of the way, in the next page, I will provide the source files needed to see these algorithms working for yourself in Flash.

Onwards to the next page!

1 | 2 | 3 | 4 | 5 | 6 | 7