Introduction

In searching, the goal is to find a path (if one exists) from the start node (normally the root in a tree) to a goal node.  Since graphs can have cycles, you need a systematic method to ensure that you do not get into an infinite loop.  Two basic methods exist -- depth-first search (DFS) and breadth-first search (BFS).

In depth-first seach, when you start on a path, you exhaust it before examining another.  For example, imagine that you take a wrong turn when you are driving and you don't want to admit that you took a wrong turn.  Then, rather then backtrack immediately to where you took the wrong turn, you would first try every possible side road to see if there was a still a way to get to your goal from the wrong turn.

In breadth-first search, you check each path the same distance before rotating through all possible paths again.  Using the driving example again, you would drive a set distance (e.g. to where your next turn should be) after taking your wrong turn.  You would then realize that you haven't reached the goal, and you would go back to the wrong turn and try the directions again from there.
 

Resources

• To see how DFS works on a tree, try this example.  On the first pass through the tree, the animation shows you the order in which the nodes will get expanded during a DFS.  Then on the second pass, the animation performs a DFS.  By trying to find different nodes, you should observe that the number of nodes visited changes, but the order in which the nodes are visited (for the same tree) doesn't change.
• You may also wish to see DFS on a graph.
• To see how BFS works on a tree, try this example.  Notice how nodes are now expanded top-to-bottom, left-to-right until the target is found.
• You may also wish to see BFS on a graph.
• For a comparison of DFS and BFS, try using both methods to solve mazes.  Notice that for a graph with many solutions (i.e. a large number of cycles), DFS can miss a short solution but BFS usually takes much longer to find the solution if no short solution exists.