16.4: Depth-first and breadth-first searches
- Page ID
- 83486
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Let \(G\) be a graph. Given vertices \(v,v'\) of \(G\text{,}\) we might wish to find a path from \(v\) to \(v'\text{,}\) if one exists. We can do this by constructing a tree \(T \preceq G\text{.}\)
To create a tree \(T\) that is a subgraph of a graph \(G\) wherein a path (in \(G\)) from \(v\) to \(v'\) is evident, begin with \(T\) containing the single vertex \(v\) and no edges. Set \(x=v\text{.}\)
- Look for a vertex \(y\) of \(G\) which is adjacent to \(x\) but not already in \(T\text{.}\) If such a \(y\) is found, go to Step 2. Otherwise, go to Step 3.
- Adjoin \(y\) and a single edge between \(x\) and \(y\) to \(T\text{.}\) If \(y = v'\text{,}\) stop — a path from \(v\) to \(v'\) exists and is now contained in \(T\text{.}\) Otherwise, set \(x=y\) and return to Step 1.
- If you have arrived here immediately after beginning the algorithm (i.e. with \(x\) still set to be \(v\)), stop — there is no path from \(v\) to \(v'\text{.}\) Otherwise, return to the vertex \(z\) adjoined before \(x\text{.}\) Set \(x = z\) and return to Step 1.
In Step 1 of the algorithm, there is no specification on how to choose a single \(y\) satisfying the search criteria from multiple possibilities. In other words, there is flexibility in the implementation of the algorithm here, and for the problem at hand there may be implementation choices that are more expedient then others.
We perform a Depth-first search on the graph in Figure \(\PageIndex{1}\), attempting to find a path from vertex \(1\) to vertex \(9\text{.}\)
In carrying out the algorithm, if we always choose the vertex with the smallest label in Step 1, we obtain the graph in Figure \(\PageIndex{2}\) (a). The graph in Figure \(\PageIndex{2}\) (b) is the result of always choosing the vertex with the largest label.
The depth-first search will not necessarily yield the shortest path from \(v\) to \(v'\text{.}\) The following algorithm will.
To create a tree \(T\) that is a subgraph of a graph \(G\) wherein the shortest path in \(G\) from \(v\) to \(v'\) is evident, begin with \(T\) containing the single vertex \(v\) and no edges.
- For each vertex \(x\) in \(T\) added in the last application of this step (or, in the case of the first application of this step, for \(x = v\)), adjoin all vertices of \(G\) that are adjacent to \(x\) and not already in \(T\text{,}\) along with a single edge between each such vertex and \(x\text{.}\) If at least one vertex has been adjoined to \(T\) in this step, proceed to Step 2. Otherwise, stop — there is no path from \(v\) to \(v'\) in \(G\text{.}\)
- If \(v'\) was one of the vertices adjoined in Step 1, stop — a path from \(v\) to \(v'\) exists and is now contained in \(T\text{.}\) Otherwise, return to Step 1.
Below is the result of the breadth-first algorithm, carried out to find a path from \(1\) to \(9\) in the graph in Figure \(\PageIndex{1}\) from Example \(\PageIndex{1}\).
