Depth-first search (DFS)

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.