by kirupa 
13 January 2006In the
previous page, you learned how to
use Depth First Search to find a solution to a search problem. In this page, I
will explain how Breadth First Search will find a solution to a similar search
problem.
Breadth First Search
The reason I cover both depth and breadth first search methods in the same
tutorial is because they are both similar. In depth first search, newly explored
nodes were added to the beginning of your Open list. In breadth first
search, newly explored nodes are added to the end of your Open list.
Let's see how that change will affect our results. For
reference, here is our original search tree:
Let's try to find a path between nodes A and E.
Step 0
Let's start with our root/goal node:
Like before, I will continue to employ the Open and Closed
Lists to keep track of what needs to be done:

Open List: A

Closed List: <empty>
Step 1
Now, let's explore the neighbors of our A node. So far, we are following in
depth first's foot steps:
We remove A from our Open list and add A to our Closed List.
A's neighbors, the B and C nodes, are added to our Open list. They are added to
the end of our Open list, but since our Open list was empty (after removing
A), it's hard to show that in this step.
Our current Open and Closed Lists contain the following data:

Open List: B, C

Closed List: A
Step 2
Here is where things start to diverge from our depth first search method. We
take a look the B node because it appears first in our Open List. Because B
isn't our intended destination, we explore its neighbors:
B is now moved to our Closed List, but the neighbors of B, nodes
D and E are added to the end of our Open list:

Open List: C, D, E

Closed List: A, B
Step 3
We now expand our C node:
Since C has no neighbors, all we do is remove C from our
Open List, add it to the end of our Closed List, and move on:

Open List: D, E

Closed List: A, B, C
Step 4
Similar to Step 3, we expand node D. Since it isn't our destination, and it too does not have any neighbors,
we simply remove D from our to Open list, add D to our Closed List, and continue on:

Open List: E

Closed List: A, B, C, D
Step 5
Because our Open list only has one item, we have no choice but to take a look at node
E. Since node E is our destination, we can stop here:
Our final versions of the Open and Closed Lists
contain the following data:

Open List: <empty>

Closed List: A, B, C, D, E
Traveling from A to E takes you through B, C, and
D using breadth first search. In the next page, I will summarize the
algorithm for both our search methods and cover the Flash code needed to
recreate them.
Onwards to the next page!
