Depth First and Breadth First Search - Page 4

From the previous page (and prior pages), you learned how to solve search problems by hand. Now, it's time for the next step. It is time to help your computer to solve the search problems also.

Pseudocode / Informal Algorithms
Now that you have a good idea on how to solve these various search problems, you need to translate them so that a computer can solve it. Before we get into the code, let's solve it generally using pseudocode, or if you prefer a better name, an informal algorithm.

Depth First Search
The pseudocode for depth first search based on what we did in Page 2 is:

1. Declare two empty lists: Open and Closed.

2. Add Start node to our Open list.

3. While our Open list is not empty, loop the following:
    

   1. Remove the first node from our Open List.

   2. Check to see if the removed node is our destination.
       

      1. If the removed node is our destination, break out of the loop, add the node to our Closed list,  and return the value of our Closed list.

      2. If the removed node is not our destination, continue the loop (go to Step c).

   3. Extract the neighbors of our above removed node.

   4. Add the neighbors to the beginning of our Open list, and add the removed node to our Closed list. Continue looping.

Breadth First Search
The pseudocode for breadth first first search is similar to what you see above, and it is based on what we did in page 3 is:

1. Declare two empty lists: Open and Closed.

2. Add Start node to our Open list.

3. While our Open list is not empty, loop the following:
    

   1. Remove the first node from our Open List.

   2. Check to see if the removed node is our destination.
       

      1. If the removed node is our destination, break out of the loop, add the node to our Closed list,  and return the value of our Closed list.

      2. If the removed node is not our destination, continue the loop (go to Step c).

   3. Extract the neighbors of our above removed node.

   4. Add the neighbors to the end of our Open list, and add the removed node to our Closed list.

The Pseudocode Converted to Flash Syntax
The following is Depth First search in ActionScript using methods from the Graph ADT:

searchMethod = function () {

var origin:Node = nodeOrigin;

var destination:Node = nodeDestination;

// 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);

 

// Loop while openList contains some data.

while (openList.length != 0) {

// Loop while openList contains some data.

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

 

// Check if node is Destination

if (n == destination) {

closedList.push(destination);

trace("Closed!");

break;

}

 

// Store n's neighbors in array

var neighbors:Array = n.getNeighbors();

var nLength:Number = neighbors.length;

 

// Add each neighbor to the beginning of our openList

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

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

}

 

// Add current node to closedList

closedList.push(n);

}

};

Not to be left behind, you now have the AS-version of Breadth First Search:

searchMethod = function () {

var origin:Node = nodeOrigin;

var destination:Node = nodeDestination;

// 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);

 

// Loop while openList contains some data.

while (openList.length != 0) {

// Loop while openList contains some data.

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

 

// Check if node is Destination

if (n == destination) {

closedList.push(destination);

trace("Closed!");

break;

}

   

// Store n's neighbors in array

var neighbors:Array = n.getNeighbors();

var nLength:Number = neighbors.length;

 

// Add each neighbor to the end of our openList

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

openList.push(neighbors[i]);

}

 

// Add current node to closedList

closedList.push(n);

}

};

On the next page, I will go through each line of code and explain what exactly it does and how it helps your computer to solve a search problem.

Onwards to the next page!

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