Depth-first search (DFS)

Depth-first search (DFS) --- поиск в глубину.

1. Let [math]\displaystyle{ G }[/math] be a directed graph.

It is convenient to formulate DFS as a recursive procedure [math]\displaystyle{ DFS(v) }[/math] with a vertex [math]\displaystyle{ v }[/math] as a parameter. In general, we search for unexplored vertices by traversing an unexplored arc from the most recently reached vertex which still has unexplored arcs. The set [math]\displaystyle{ REACH }[/math] contains the explored vertices. On these conditions [math]\displaystyle{ DFS }[/math] has the following main structure

[math]\displaystyle{ \begin{array}{l} \mbox{procedure } DFS(v:V) \\ \mbox{ begin} \\ ~~~~~\mbox{add } v\mbox{ to }REACH; \\ ~~~~~\mbox{for } \forall w\mbox{ with }(v,w) \in E\mbox{ do} \\ ~~~~~~~~~~\mbox{if } w \not \in REACH\mbox{ then } DFS(w)\mbox{ fi} \\ ~~~~~\mbox{od} \\ \mbox{end} \end{array} }[/math]

The procedure starts with

[math]\displaystyle{ \begin{array}{l} REACH \leftarrow \emptyset; \\ DFS(r); \end{array} }[/math]

and marks all vertices reachable from the start vertex [math]\displaystyle{ r }[/math]. But [math]\displaystyle{ DFS }[/math] gives some further information about the digraph [math]\displaystyle{ G }[/math]. In particular, [math]\displaystyle{ DFS }[/math] computes the so-called depth-first search tree (or [math]\displaystyle{ DFS }[/math]-tree) with a root [math]\displaystyle{ r }[/math], which consists of all vertices reachable from the vertex [math]\displaystyle{ r }[/math]. If [math]\displaystyle{ G }[/math] is a cf-graph with an initial vertex [math]\displaystyle{ r }[/math], then [math]\displaystyle{ DFS }[/math]-tree is a spanning tree of [math]\displaystyle{ G }[/math]. [math]\displaystyle{ DFS }[/math] can be easily extended in such a way that for any cf-graph [math]\displaystyle{ G }[/math] with an initial vertex [math]\displaystyle{ r }[/math], [math]\displaystyle{ DFS(r) }[/math] computes in a linear time two correlated basic numberings of [math]\displaystyle{ G }[/math] and makes the corresponding partition of all arcs of [math]\displaystyle{ G }[/math] into the four classes of the tree, forward, backward and cross arcs with respect to the basic numberings.

2. Let [math]\displaystyle{ G }[/math] be an undirected graph.

Suppose that in a depth-first search of an undirected graph we are currently visiting a vertex [math]\displaystyle{ v }[/math]. The general step in the search then requires that the next visited is a vertex adjacent to [math]\displaystyle{ v }[/math] which has not yet been visited. If no such vertex exists, then the search returns to the vertex visited just before [math]\displaystyle{ v }[/math] and the general step is repeated until every vertex in that component of the graph becomes visited. Such a search cannot revisit a vertex except by returning to it via edges that have been used since the previous visit. Hence, the edges traversed in a depth-first search form a spanning tree for each separate component of the graph. This set of trees is mathcalled a depth first spanning forest [math]\displaystyle{ F }[/math]. Thus, [math]\displaystyle{ DFS }[/math] partitions the edges [math]\displaystyle{ E }[/math] into two sets, [math]\displaystyle{ F }[/math] and [math]\displaystyle{ B = E \setminus F }[/math]. The edges in [math]\displaystyle{ B }[/math] are mathcalled back-edges.

The time complexity of DFS in a general case is [math]\displaystyle{ O(n + m) }[/math]

References

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.