What is the difference between breadth first search and best first search?

Answer 1

The main difference is that depth-first uses a stack while breadth-first uses a queue.

To illustrate, imagine a binary tree where every node has up to two child nodes and some data. We begin at the root in both cases. With breadth-first, we enqueue the root. We then begin an iterative process. First, we dequeue a node. If the node contains the data being sought then we're done. Otherwise we enqueue the node's immediate children. If the queue is empty, the data being sought does not exist and we're done. Otherwise we begin a new iteration.

With depth first we do the same thing except we stack the nodes (push and pop rather than enqueue and dequeue). Queues are a FIFO structure (first in, first out) while stacks are LIFO (last in, first out). This dramatically alters the sequence in which nodes are examined. Breadth-first examines nodes in sequence, row by row, whereas depth-first examines the depths of the left hand side of each node before examining the depths of the right hand side of each node.

Depth-first is ideally suited to brute force backtracking algorithms (particularly NP-complete problems) as well as for rapidly building sorted lists from unsorted sequential data. Breadth-first search is better suited to creating diagrams from binary trees because a single pass can determine the number of levels and the maximum width required to display the tree, while a second pass can build the diagram one row at a time (typical breadth-first implementations will maintain the width and height as internal members to avoid recalculating them).

Because depth-first employs a stack, implementations often make use of recursion rather than iteration, thus taking advantage of the call stack to provide the necessary backtracking. However, an iterative approach is usually more efficient, particularly if the tree depth exceeds the compiler's ability to inline expand the recursions.

Answer 2

Both algorithm can be build very similar. The difference between breadth first search and depth first search is order in which element are added to open list.

In Breadth First Search :- A new node are appended to the end of open list.

in addition it needs Memory Space.

In Depth First Search :- A new node are inserted in the beginning of open list.

Answer 3

Both methods make use of recursion to traverse a tree of nodes starting at the root node, visiting every node until the value being sought is found. Which method you use will depend on whether the data is more likely to appear in the upper levels of the the tree (at or near the root node) or in the lower levels (at or near the leaf nodes). The former uses breadth-first while the latter uses depth-first.

If we assume a node has the following simplified structure:

class cnode

{

public:

cnode* searchbreadth(int value);

cnode* searchdepth(int value);

cnode* m_head;

cnode* m_next;

int value;

};

Then the breadth-first search would be implemented like this:

cnode* cnode::searchbreadth(int value)

{

cnode* found = 0;

if( m_value value )

return( this );

return( found );

}

As you can see the only real difference is whether the comparison is done before or after the recursive traversal. For depth first, you must traverse first, for breadth first, you must compare first.

Note that binary-trees must always use a depth-first search since all data is contained in the leaf nodes. However, the above implementations are unsuitable for binary trees since binary trees are constructed from an abstract node which implements the search method as a traversal of the root and parent (or internal) nodes, while the leaf nodes override the search method to perform the actual comparison with itself. Other than that, the principal is the same.

Answer 4

The main difference is that with depth first we use a stack to backtrack and with breadth first we use a queue. Which method we use is ultimately determined by the ordering of the tree.