Search involves visiting nodes in a tree in a systematic manner, and may or may not result into a visit to all nodes. When the search necessarily involved the examination of every vertex in the tree, it is called the traversal.
Traversing of a tree can be done in two ways.
- Depth first search or traversal.
- Breadth first search or traversal.
Depth first search:
In Depth first search, we begin with root as a start state, then some successor of the start state, then some successor of that state, then some successor of that and so on, trying to reach a goal state. One simple way to implement depth first search is to use a stack data structure consisting of root node as a start state.
If depth first search reaches a state S without successors, or if all the successors of a state S have been chosen (visited) and a goal state has not get been found, then it “backs up” that means it goes to the immediately previous state or predecessor formally, the state whose successor was ‘S’ originally.
To illustrate this let us consider the tree shown below.
Suppose S is the start and G is the only goal state. Depth first search will first visit S, then A, then D. But D has no successors, so we must back up to A and try its second successor, E. But this doesn’t have any successors either, so we back up to A again. But now we have tried all the successors of A and haven’t found the goal state G so we must back to ‘S’. Now ‘S’ has a second successor, B. But B has no successors, so we back up to S again and choose its third successor, C. C has one successor, F. The first successor of F is H, and the first of H is J. J doesn’t have any successors, so we back up to H and try its second successor. And that’s G, the only goal state.
So the solution path to the goal is S, C, F, H and G and the states considered were in order S, A, D, E, B, C, F, H, J, G.
Disadvantages:
1. It works very fine when search graphs are trees or lattices, but can get struck in an infinite loop on graphs. This is because depth first search can travel around a cycle in the graph forever. To eliminate this keep a list of states previously visited, and never permit search to return to any of them.
2. We cannot come up with shortest solution to the problem.
Breadth first search:
Breadth-first search starts at root node S and “discovers” which vertices are reachable from S. Breadth-first search discovers vertices in increasing order of distance. Breadthfirst search is named because it visits vertices across the entire breadth.
To illustrate this let us consider the following tree:
Breadth first search finds states level by level. Here we first check all the immediate successors of the start state. Then all the immediate successors of these, then all the immediate successors of these, and so on until we find a goal node. Suppose S is the start state and G is the goal state. In the figure, start state S is at level 0; A, B and C are at level 1; D, e and F at level 2; H and I at level 3; and J, G and K at level 4.
So breadth first search, will consider in order S, A, B, C, D, E, F, H, I, J and G and then stop because it has reached the goal node.
Breadth first search does not have the danger of infinite loops as we consider states in order of increasing number of branches (level) from the start state.
One simple way to implement breadth first search is to use a queue data structure consisting of just a start state.
