[wptelegram-join-channel]

### Depth-first search (DFS)

Breadth-First –Search is an uninformed search technique. We may sometimes search the goal along with the largest depth of the tree, and move up only when further traversal along the depth is not possible. We then attempt to find alternative offspring of the parent of the node (state) last visited. If we visit the nodes of a tree using the above principles to search the goal, the traversal made is called depth-first traversal and consequently, the search strategy is called depth-first search

Algorithm: Depth-First Search

```1. If the initial state is a goal state, quit and return success.

2. Otherwise, do the following until success or failure is signaled:
a) Generate a successor, E, of the initial state.
If there are no more successors, signal failure.
b) Call Depth-First Search with E as the initial state.
a) If success is returned, signal success. Otherwise continue in this loop
```

### Depth-First Search – Example

Let us consider the following tree. Here node ‘A’ is the source or start or initial node and node ‘G’ is the goal node.

Step 1: Initially NODE-LIST contains only one node corresponding to the source state A.

NODE-LIST: A

Step 2: Node A is removed from NODE-LIST. A is expanded and its children B and C are put in front of NODE-LIST.

NODE-LIST: B C

Step 3: Node B is removed from NODE-LIST, and its children D and E are pushed in front of NODE-LIST.

NODE-LIST: D E C

Step 4: Node D is removed from NODE-LIST. C and F are pushed in front of NODE-LIST.

NODE-LIST: C F E C

Step 5: Node C is removed from NODE-LIST. Its child G is pushed in front of NODE-LIST.

NODE-LIST: G F E C

Step 6: Node G is expanded and found to be a goal node.

NODE-LIST: G F E C

The solution path A-B-D-C-G is returned and the algorithm terminates.

Depth-first search requires less memory since only the nodes on the current path are stored. This contrasts with breadth-first search, where all of the trees that have so far been generated must be stored.

The depth-first search may find a solution without examining much of the search space at all. This contrasts with breadth-first search in which all parts of the tree must be examined to level n before any nodes on level n + i can be examined. This is particularly significant if many acceptable solutions exist. Depth-first search can stop when one of them is found.