16.4: Búsquedas en profundidad y primero en profundidad
- Page ID
- 118072
\( \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}\)\(G\)Déjese ser una gráfica. Dados los vértices\(v,v'\) de\(G\text{,}\) podríamos desear encontrar un camino de\(v\) a\(v'\text{,}\) si existe uno. Podemos hacer esto construyendo un árbol\(T \preceq G\text{.}\)
Para crear un árbol\(T\) que sea un subgrafo de una gráfica\(G\) donde\(v'\) sea evidente un camino (in\(G\)) de\(v\) a, comience por\(T\) contener el vértice único\(v\) y sin aristas. Set\(x=v\text{.}\)
- Busque un vértice\(y\) del\(G\) cual esté adyacente\(x\) pero no ya en\(T\text{.}\) Si\(y\) se encuentra tal, vaya al Paso 2. De lo contrario, vaya al Paso 3.
- Adjoin\(y\) y un solo borde entre\(x\) y\(y\) a\(T\text{.}\) If\(y = v'\text{,}\) stop:\(v'\) existe una ruta de\(v\) a y ahora está contenida en\(T\text{.}\) De lo contrario, establezca\(x=y\) y vuelva al Paso 1.
- Si ha llegado aquí inmediatamente después de comenzar el algoritmo (es decir, con\(x\) todavía establecido para ser\(v\)), deténgase — no hay ruta de\(v\) a De\(v'\text{.}\) lo contrario, regrese al vértice\(z\) contiguo antes de\(x\text{.}\) Set\(x = z\) y regrese al Paso 1.
En el Paso 1 del algoritmo, no hay ninguna especificación sobre cómo elegir una sola que\(y\) satisfaga los criterios de búsqueda desde múltiples posibilidades. En otras palabras, aquí hay flexibilidad en la implementación del algoritmo, y para el problema que nos ocupa puede haber opciones de implementación que sean más expeditas que otras.
Realizamos una búsqueda de profundidad primero en la gráfica de la Figura\(\PageIndex{1}\), intentando encontrar una ruta de vértice\(1\) a vértice\(9\text{.}\)
Al llevar a cabo el algoritmo, si siempre elegimos el vértice con la etiqueta más pequeña en el Paso 1, obtenemos la gráfica en la Figura\(\PageIndex{2}\) (a). La gráfica de la Figura\(\PageIndex{2}\) (b) es el resultado de elegir siempre el vértice con la etiqueta más grande.
La búsqueda en profundidad primero no necesariamente arrojará el camino más corto de\(v\) a\(v'\text{.}\) El siguiente algoritmo lo hará.
Para crear un árbol\(T\) que sea un subgrafo de una gráfica en\(G\) donde el camino más corto en\(G\) de\(v\) a\(v'\) sea evidente, comience por\(T\) contener el vértice único\(v\) y sin aristas.
- Por cada vértice\(x\) en\(T\) agregado en la última aplicación de este paso (o, en el caso de la primera aplicación de este paso, para\(x = v\)), colindan todos los vértices de los\(G\) que son adyacentes a\(x\) y no ya adentro\(T\text{,}\) junto con un solo borde entre cada tal vértice y\(x\text{.}\) Si se ha colindado al menos un vértice\(T\) en este paso, proceda al Paso 2. De lo contrario, detente — no hay camino de\(v\) a\(v'\) adentro\(G\text{.}\)
- Si\(v'\) fue uno de los vértices contiguos en el Paso 1, deténgase —\(v'\) existe un camino de\(v\) a y ahora está contenido en\(T\text{.}\) De lo contrario, regrese al Paso 1.
A continuación se muestra el resultado del algoritmo de amplitud primero, llevado a cabo para encontrar una ruta de\(1\) a\(9\) en la gráfica de la Figura\(\PageIndex{1}\) de Ejemplo\(\PageIndex{1}\).
