Depth-first search (DFS)

Материал из WikiGrapp
Перейти к:навигация, поиск

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

1. Let G be a directed graph.

It is convenient to formulate DFS as a recursive procedure DFS(v) with a vertex v 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 REACH contains the explored vertices. On these conditions DFS has the following main structure


\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}

The procedure starts with


\begin{array}{l}
REACH \leftarrow \emptyset; \\
DFS(r);
\end{array}

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

2. Let G be an undirected graph.

Suppose that in a depth-first search of an undirected graph we are currently visiting a vertex v. The general step in the search then requires that the next visited is a vertex adjacent to v which has not yet been visited. If no such vertex exists, then the search returns to the vertex visited just before v 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 F. Thus, DFS partitions the edges E into two sets, F and B = E \setminus F. The edges in B are mathcalled back-edges.

The time complexity of DFS in a general case is O(n + m)

References

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