Wikibooks

Artificial Intelligence/Search/Heuristic search/Depth-first search

< Artificial Intelligence | Search

Background and Definition

edit

Depth-first search is an algorithm used to find information represented in a graphical format. The first version of depth-first search, originally called Tremaux’s algorithm, was designed as a means of solving mazes in the nineteenth century (Stewart, 1999). [The] “theoretical properties of Tremaux’s maze solving method,” however, where not discovered in the field of computer science until 1970 when John Hopcroft and Robert Tarjan collaborated, using depth-first search to “obtain linear time algorithms” (Tarjan, 1972, p. 146).

An algorithm, a word originally coined by mathematician Mohammed ibn-Musa al-Khwarizmi in the late 700s CE, is a procedure or formula used to find a solution to a problem (Berardi, Kroon, McDermott & Newton, 2006). Algorithms work with various inputs; these inputs often vary in the amount of information they contain. A good algorithm must be able to efficiently organize input of any length into basic functional steps that can be stored in the memory of the program (“PC”, 2008). Hopcroft and Trajan’s linear time algorithms equalized the size of the input to the amount of resources and time spent by the program to solve a particular problem (Tarjan, 1972).

The depth-first search algorithm is used to vertically traverse nodes of information of a graph formatted in a tree structure. Beginning with a single node at the top of the graph, the search moves to each subsequent node, vertically, starting with the left-most side of the tree structure until the search reaches the bottom-most node of the tree structure. The search does not move horizontally from left to right until the search of each node on one segment of the tree structure is complete (Siek & Lee, 2000).

One of the most important features for a depth-first search is the ability to keep track of the nodes that have already been visited. The following pseudocode allows for this feature. 

DFS(u):

visit(u);
time = time + 1;
d[u] = time;
color[u] = grey;

for all nodes v adjacent to u do
   if color[v] == white then
      p[v] = u;
       DFS(u);


time = time + 1;
f[u] = time;
color[u] = black;

Created by Kravitz, David and Lafferty (1997) this pseudocode shows how a depth first search algorithm works by efficiently keeping track of the nodes already visited and the nodes still left to explore. Kravitz et al. made each node to be explored white, each node being explored grey, and each node that had been explored black. The color coding of the nodes allows the user the track the progress of the search algorithm as well as keeping an accurate data map of which nodes have already been stored. The first line in the code initializes the depth first search, starting with the left most tree segment on the graph. 

DFS(u):

This block of code allows the search engine to visit every node on the left most tree segment of the tree structure, turning the nodes from white to grey as they are searched one time. 

visit(u);
time = time + 1;
d[u] = time;
color[u] = grey;

This block of code moves the search across the tree structure horizontally, from left to right once every node on the left side of the tree structure has been searched once. In other words, the algorithm moves toward the white nodes. When the algorithm is done searching a node, the node is turned black, and the algorithm cannot re-search that node again. 

for all nodes v adjacent to u do
   if color[v] == white then
      p[v] = u;
       DFS(u);


time = time + 1;
f[u] = time;
color[u] = black;

Practical Application

edit

One practical application for depth-first search is “an algorithm to determine whether a graph is planar” (“Graph,” 2008). Basically a planar graph can be drawn in a plane without graph edges crossing (Weisstein, 2008). Depth-first search enables the user to organize the information represented in the graph “by post-order traversal of the tree [structure]” (“Planar,” 2008). In other words, depth-first search gives the user the ability to decide the order they want to “embed back edges from” the first node to each following node. If, during this process, the user decides that a certain grouping of nodes have potential connections to other nodes not presently represented on the tree structure graph, then the user will know that that particular tree segment must “be kept on the external face” of the planar graph (“Planar,” 2008).

Problem

edit

In depth-first search “each node has two times associated with it: the discovery time and the finish time” (Kravitz, David & Lafferty, 1997). If the search parameter is large (i.e., a large amount of nodes) then “the storage required for all of these times becomes” quickly unmanageable (Kravitz, David & Lafferty, 1997).

References

edit
Retrieved from "https://en.wikibooks.org/w/index.php?title=Artificial_Intelligence/Search/Heuristic_search/Depth-first_search&oldid=3222334"