More Info about DFS and BFS

Depth-First Search

• Same basic idea as in recursive traversal of binary trees

pseudocode Algorithm:

*note: this is not java, just logic

boolean depthFirstsearch (OpenNodes; GoalNode)

{

        if there are no more OpenNodes

        then you're done, return false

    else

        if the first OpenNode is the GoalNode

            then you're done, return true

    else

        {

        take the first openNode off the Open Nodes list

        find all its adjacent nodes by calling GetAdjacentNodes

        put them all in front of the OpenNodes lsit

        call depthFirstSearch again with the new OpenNodes list

        }

}// end of depthFirstSearch

• This version doesn't keep track of the actual path that is found, just returns true or false
• In practice, you'd want the algorithm to return the Path from the beginning point to the goal
• It doesn't check for cycles (repetitive visits)
• In depth-first search, are treating the list of OpenNodes as a stack:  * adding to the front (i.e, top) of the stack, and exploring the most recently added nodes first

Below is an example of a binary tree searched using DFS.

DFS begins at the top node, as shown here, and searches to the left as far as it can go and then goes to the right.  The numbers depict the order in which the graph was searched.

The binary search above shows the idea of depth-first search.  Now, let's look at an application of this idea:

Suppose, for example, you were given the following graph that indicated miles between cities (unrealistic) and gave you the possible paths you could use to travel.

okay, now determine if there is a route from Buffalo to Orlando.

Since DFS uses the same basic idea as recursive traversals of binary trees, you would solve the problem the following way:

1. Start with Buffalo

2. Find all cities within a single hop (Chicago, New York, and Orlando)

3. Pick 1st (Chicago), see if some route from Chicago will get to Orlando  (using same idea, recursively) so...

4. Find all cities within a single hop( Buffalo, Miami, Orlando, Pittsburgh)

5. Pick 1st (Buffalo : reject), then 2nd (Miami: keep)

6. Pick 1st (Atlanta)

7. etc., etc.

See!  DFS goes DOWN as far as possible before it goes across.  Thus, it may find a longer path than neccesary.  Requires some means of preventing cyclic searches (like keeping track of cities already visited).

Breadth-First Search

• Similer to Depth-First Search
• Difference in order in which nodes are considered
• Breadth-First Search goes "side to side" and uses a queue

pseudocode algorithm:

*note: this is not java

boolean breadthFirstSearch (OpenNodes; GoalNode){

    if there are no more OpenNodes

        then you're done, return false

    elseif the first OpenNode is the GoalNode

        then you're done, return true

    else{

        dequeue an OpenNode from the OpenNodes list

        find all its adjacent nodes (call GetAdjacentNodes)

        enqueue them all at the end of the OpenNodes list

        call BreadthFirstSearch again with the new OpenNodes list}

    endif

}/ end breadthFirstSearch

Below is an example of a binary tree searched by a breadth-first search.   One way of looking at a breadth-first search is to take a pencil, lay it horizontally on the paper, above the graph.  As you bring the pencil towards you, you will reveal more and more of the graph.  The order in which these nodes appear is the order in which a breadth-first search would search the graph.

Now, suppose you were given that same graph that indicated miles between cities (unrealistic) and gave you the possible paths you could use to travel.

This time, determine if there is path from Buffalo to Miami:

Using a BFS, the search is done a little differently than seen in the DFS:

1. Consider Buffalo's adjacent nodes by collecting them into the "open list" (for BFS, a queue), giving us Chicago, New York, and Orlando.

2. Then, dequeue from the list, considering each in turn:  Is Chicago the goal node?  no, so put its adjacent nodes on the "open list", giving us the list Newyork, Orlando, Miami, Pittsburgh, Sao Paulo  (note:  this is a dumb algorithm, meaning it doesn't realize that it just found Miami, all it "knows" is that it's going through the nodes in the prescribed order)

3. Dequeue from the list, consider New York:  is New York the goal node?   No, so put it's adjacent nodes on the "open list".  Now, our list includes Orlando, Miami, Pittsburgh, Sao Paulo, Orlando, and Pittsburgh (again).

4. Dequeue from the list, consider Orlando:  is Orlando the goal node?   No, so put it's adjacent nodes on the "open list".  Now, our list includes Miami, Pittsburgh, Sao Paulo, Orlando, and Pittsburgh (again), and New York.

5. Dequeue from the list, consider Miami:  is Miami the goal node?   YES!!!!!!!  Bingo!  so, we return true.

This returns a BOOLEAN result, you must modify it to return the path it found, not just whether or not it found one.

• Both Depth-First Search and Breadth-First Search are chronological, meaning they do not attempt to make any decisions about what's best to do.  In a binary search tree, as shown above, it doesn't make a difference but in an n-ary search, there are huge issues.
• Making complete judgement about the best path would involve exponential work, so there are other approaches to determining the best path:  A Greedy Search is one of those. 

page design: Heather Macleod gte854e