Depth-first search

Depth-first search (English depth -first search, DFS) is in computer science, a method for finding nodes in a graph. It is one of the uninformed search algorithms. In contrast to the breadth-first search, a path is completely trodden into the depths, before branching paths are trodden in the depth- first. Here are all reachable nodes of the graph are visited. For graphs with potentially few long paths to the limited depth- offers, where each path is taken only up to a certain depth.

An improvement in the depth-first search is the iterative deepening search.

General

Depth-first search is an uninformed search, which further investigated by expansion of each first occurring successor node in the graph gradually from the start node to the depths. The order in which the successors of a node are also determined and depends on the representation of the successor. In the representation of a adjacency list using a linked list, for example, the nodes are traversed in the order of their entry in this list. In the above image is implicitly assumed that the successor be chosen " from left to right".

For undirected graphs, the method is as follows: First, a starting node is selected. From this node of the first edge is now viewed and tested whether the opposite node was already discovered or the searched element. If this is not the case, is called recursively for the node depth-first search, which again, the first successor of this node is expanded. This type of search will continue until the search item was either found or the search has arrived at a sink in the graph and thus can not investigate further successor node more. At this point, the algorithm now returns to the last expanded node and examined the next successor of the node. If there are no other successor more here, the algorithm step by step to its predecessor goes back and tried it again there. An example of the application of the depth-first search on a tree can be found in the above file.

The edges of the graph, which are used by the depth-first search algorithm to traverse the graph are called tree edges. Those edges that are not used and lead from one node to another node in the same subtree that is visited in the depth-first search later called forward edges. Those edges that are not used and lead from one node to another node in the same subtree that has already been visited in the depth-first search beforehand called backward edges. Those edges that extend " crosswise " of a subtree to another subtree hot transverse edges. Within the depth of the search tree, the path between two nodes connected by a transverse edge would first require a set-up and then a descent in the tree. Forward edges, backward edges, cross edges and tree edges give a total of the edge set of the graph.

Algorithm ( informal)

• If the stack should be empty, do nothing
• If there are no undeveloped successor more, delete the top node from the stack and calls for the now top node in the stack DFS (depth first search or depth-first search ) on
• If the searched element should have been found, break off the search and deliver a result

Algorithm (formal)

DFS (node ​​, goal ) {    if ( node == goal ) {      return node;    else }    {      stack: = expand ( node)      while ( stack is not empty )      {        node ': = pop ( stack);        DFS ( node ', goal );      }    } } Algorithm Example: generating the depth-first search forest (recursively)

The following recursive algorithm generates the depth-first search forest of a graph G by setting Discovery and finishing Times and coloring the nodes. Following Cormen et. al. are first dyed all nodes white. Then the depth-first search starts by definition at the alphabetically smallest node and colors these gray. Thereafter, as described above recursively considers its neighboring white and gray. If there is no white neighbor more, it comes to backtracking, during which all wandered nodes are colored black.

DFS (G ) Color 1 for each v of G {/ / All nodes know predecessor set to nil 2 col [v ] = ' w'; 3 pi [v ] = nil; 4} 5 time = 0; / / 6 for each u of G for all white nodes: call DFS -visit 7 if col [ u] == ' w' 8 DFS -visit (u ); DFS -visit (u ) 1 col [ u] = ' g'; Color / / current node gray 2 time ; / Increase / time counter 3 d [ u] = time; / / Set the current node Entdeckzeit 4 for each v of Adj [u ] { / / For all the white neighbors of the current node 5 if col [v ] == ' w' { 6 pi [v ] = u; / / Set the predecessor to the current node 7 DFS -visit (v ); / Call / DFS -visit 8} 9} 10 col [ u] = ' s'; Color / / current node black 11 time ; 12 f [ u] = time; / / Set the finishing time of the current node properties

In the following, memory consumption and running time of the algorithm in Landau notation be specified. We also assume a directed graph.

Space

The memory consumption of the algorithm without the space for the graph, as it is passed, given, because this can be in various forms with different memory usage, eg as a linked list, as adjacency matrix or incidence matrix.

Initially all nodes are colored white and put their parents on the Nile for the above procedure DFS (G). Thus, this information needs constant space, ie O (1) for each node. Overall, a linear memory consumption of O ( | V | ), depending on the number of nodes | V | (german vertices ). The memory consumption of the variable time is a constant O (1) to O ( | V | ) negligible. Then, for each node u, the procedure DFS -visit (u ) is called. Since this is just about control structures, they do not contribute to memory consumption.

DFS -visit procedure (u) operates on the already established memory structure in which all nodes are stored for each node and extends it to the still Entdeckzeit and finishing time, each constant O (1). That does not change the previous linear memory space consumption O ( | V | ). Because otherwise in DFS -visit (u ) no further variables will be introduced, the depth-first search has a memory consumption of.

Term

If the graph has been stored as the adjacency list, all possible paths have to be considered at all possible nodes in the worst case. Thus, the running time of depth-first search, which stand for the number of nodes and the number of edges in the graph.

If the graph is stored as an adjacency matrix, the runtime complexity is.

Completeness

If a graph is infinite or not a test is performed in cycles, the depth-first search is not complete. It may therefore be that a result - although it exists - is not found.

Optimality

Depth-first search is not optimal especially for monotonically increasing path cost as a result, may be found, for which a very much longer than the path leading to the alternative result. But is such a result I.A. found significantly faster than for the (in this case optimal, but much more expensive memory ) breadth-first search. As a combination of depth-and breadth-first search, there is the iterative deepening search.

Application

• Depth-first search is indirectly involved in many complex algorithms for graphs. One example is the finding all strongly connected components of a graph.
• In a dependency tree, the sorted finish- times result (see pseudocode above) an inverse topological sort.
• With the depth-first search can be used to test the graph at run-time to circles and output the corresponding sequence of edges in the case of circles.
• A cycle-free graph can be topologically sorted in runtime using the depth-first search.