busqueda en profundidad

BÚSQUEDA EN PROFUNDIDAD.
Muchos algoritmos de grafos necesitan visitar de un modo sistemático todos los vértices de un grafo. En la búsqueda en profundidad se avanza de vértice en vértice, marcandocada vértice visitado. La búsqueda siempre avanza hacia un vértice no marcado, internándose “profundamente” en el grafo sin repetir ningún vértice. Cuando se alcanza un vértice cuyos vecinos han sidomarcados, se retrocede al anterior vértice visitado y se avanza desde éste.

Si dado un grafo simple G, escogemos un vértice v para iniciar la exploración del grafo utilizando la búsqueda enprofundidad, el árbol que se construye es un árbol generador de la componente conexa del grafo que contiene a v. Sea G(V, E) un grafo conexo y v un vértice de V. El algoritmo de búsqueda en profundidadpuede detallarse así:
1. Se comienza en un vértice v (vértice activo) y se toma como la raíz del árbol generador T que se construirá. Se marca el vértice v.
2. Se elige un vértice u, no marcado,entre los vecinos del vértice activo. Si no existe tal vértice, ir a 4.
3. Se añade la arista (v, u) al árbol T. Se marca el vértice u y se toma como activo. Ir al paso 2.

4. Si se han alcanzadotodos los vértices de G el algoritmo termina. En caso contrario, se toma el vértice padre del vértice activo como nuevo vértice activo y se vuelve al paso 2.
La complejidad de este algoritmo esO(max{n, m})

Ejemplo 3.2.4. Hallar un árbol generador para el siguiente grafo aplicando el algoritmo
de búsqueda en profundidad.


Si no se tuviera la certeza de que el grafo G es conexo, senecesita modificar el paso 4 para permitir la búsqueda en las componentes conexas que no contienen a v. Entonces este algoritmo servirá también para hallar todas las componentes conexas del grafo G,mediante la construcción de un árbol generador de cada componente conexa de G.


Ejemplo 3.2.5. Aplicar el algoritmo de búsqueda en profundidad al siguiente grafo.



La búsqueda en profundidad se...