Depth First Search

Depth First Search (otherwise known as DFS) is a search algorithm for trees. It is an uninformed search, meaning that it does not take in any information about the cost of going to and from nodes. DFS traverses down the tree instead of traversing to the closest nodes first (Breadth First Search (BFS)).

500px-Binary_tree_structure.svg.png

Idea

DFS starts with the root node and traverses to its children. On the first child, it traverses to all of its children etc. When it gets to a node that does not have any children, it goes to its parent. To make sure that DFS does not get in a loop (child -> parent -> child etc), we must have a "visited" array that keeps track of the visited nodes.

In our encyclopedia example, we would like DFS to find the 'Science' node. First, DFS would traverse to 'Culture', and then to its children, 'Craft' and 'Art'. First we traverse to 'Craft', but since 'Craft' is not the node we would like, it goes back to 'Culture' and then to 'Art'. 'Art' is not the solution, so we go up to 'Culture'. Is 'Culture' correct? No, now let's look at the root node's other child, 'Science'. Let's traverse 'Science's children. None. Is 'Science' the answer? Yes!

DFS involves traversing to the maximum depth of a tree, then continuing and backing out continuously.

Depending on the problem, Iterative Depth First Search could be better, as it requires less memory and searches nodes that are farther down in the tree.

Pros

Using depth first search is quite memory efficient since only needs to keep the tree (duh) and the visited array in memory. If you know that the solution is going to be in a certain level, DFS will search up to that level and will not waste as much time in the upper levels.

Cons

It can be quite slow, as it is uninformed, and if the solution is in the nodes closest to the root, it will miss them

Implementation

Java implementation

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License