Busqueda en profundidad

uc3.2. Búsqueda en Profundidad. Búsqueda en anchura. Definición 3.2.1. Dado un grafo G =(V, E), un árbol generador de G, es un subgrafo que es árbol y contiene a todos los vértices del grafo. Ejemplo 3.2.2.

Proposición 3.2.3. Todo grafo conexo posee un árbol generador. Proposición 3.2.4. El grafo completo Kn tiene n n − 2 árboles generadores diferentes). Búsqueda en profundidad. Muchosalgoritmos 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, marcando cada 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 sido marcados, se retrocede al anteriorvé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 en profundidad, 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 profundidad puede detallarse así: 1. Se comienza en un vérticev (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 alcanzado todos los vértices de G el algoritmo termina. En casocontrario, 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 es O(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, se necesita modificar el paso 4 para permitir la búsqueda en las componentesconexas 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 puede implementar de forma recursiva. Debido al paso 4 del algoritmo descritoarriba, donde se regresa al padre del vértice activo, la búsqueda en profundidad es un algoritmo de retroceso o “backtracking”. Este tipo de algoritmo es de particular importancia en varios problemas de decisión, donde lo que se requiere es encontrar una solución o probar que no existe ninguna solución, por ejemplo, en el problema de la satisfacibilidad. Sean X={x1, x2,…, xn} un conjunto devariables booleanas y C={C1,...,Cm} el conjunto de cláusulas que forma la fórmula cnf S. El siguiente algoritmo de retroceso se puede utilizar para establecer si la fórmula S es satisfacible o no.
PROCEDURE SAT(S) BEGIN

IF contradiccion THEN RETURN (falso); IF “todas las variables han sido evaluadas” THEN RETURN (verdadero) Sea x una variable no evaluada; S=reducir(S,x=1) RETURN SAT(S)S=reducir(S,x=0) RETURN SAT(S) END

Este algoritmo se ha implementado utilizando la función recursiva SAT. Aquí el procedimiento reducir devuelve la fórmula cnf reducida resultante de asignarle un valor a una de las variables de la formula original. Es un algoritmo de retroceso, pues retrocede al nivel anterior cuando se encuentra una contradicción. En este problema se produce un árbol de búsqueda binario.Cada vértice del árbol representa una fórmula obtenida al asignarle un valor a una variable presente en la fórmula que se encuentra en el nivel anterior, por tanto de cada vértice sólo pueden obtenerse dos hijos. Al asignarle valor a una nueva variable se avanza en profundidad. Al encontrar una contradicción se retrocede hasta llegar al nivel de una variable a la que solo se le ha asignado uno...