7.15. Búsqueda en profundidad general¶
La gira del caballo es un caso especial de una búsqueda en profundidad donde el objetivo es crear el árbol de búsqueda en profundidad más profundo, sin ramas. La búsqueda en profundidad más general es realmente más fácil. Su objetivo es buscar lo más profundamente posible, conectando tantos nodos en el grafo como sea posible y ramificando donde sea necesario.
Incluso es posible que una búsqueda en profundidad cree más de un árbol. Cuando el algoritmo de búsqueda en profundidad crea un grupo de árboles llamamos a esto un bosque de profundidad. Al igual que con la búsqueda en anchura, nuestra búsqueda en profundidad hace uso de los enlaces a los predecesores para construir el árbol. Además, la búsqueda en profundidad hará uso de dos variables de instancia adicionales en la clase Vertice. Las nuevas variables de instancia son los tiempos de descubrimiento y de finalización. El tiempo de descubrimiento rastrea el número de pasos en el algoritmo antes de que un vértice sea encontrado por primera vez. El tiempo de finalización es el número de pasos en el algoritmo antes de que un vértice se pinte de negro. Como veremos después de examinar el algoritmo, los tiempos de descubrimiento y de finalización de los nodos proporcionan algunas propiedades interesantes que podemos usar en algoritmos posteriores.
El código para nuestra búsqueda en profundidad se muestra en el Programa 5. Puesto que las dos funciones bep y su auxiliar visitabep usan una variable para realizar un seguimiento del tiempo entre llamadas a visitabep, hemos elegido implementar el código como métodos de una clase que hereda de la clase Grafo. Esta implementación extiende la clase Grafo agregando una variable de instancia tiempo y los dos métodos bep y visitabep. Mirando la línea 11, usted notará que el método bep itera sobre todos los vértices del grafo llamando a visitabep sobre los nodos que sean blancos. La razón por la que iteramos sobre todos los nodos, en lugar de simplemente buscar desde un nodo de partida elegido, es asegurarnos de que se consideren todos los nodos en el grafo y que no haya vértices que se queden fuera del bosque de profundidad. Puede parecer inusual ver la instrucción for unVertice in self, pero recuerde que en este caso self es una instancia de la clase grafoBEP, y que iterar sobre todos los vértices en una instancia de un grafo es algo natural que hacer.
Programa 5
1from pythonds.graphs import Grafo
2class grafoBEP(Grafo):
3 def __init__(self):
4 super().__init__()
5 self.tiempo = 0
6
7 def bep(self):
8 for unVertice in self:
9 unVertice.asignarColor('blanco')
10 unVertice.asignarPredecesor(-1)
11 for unVertice in self:
12 if unVertice.obtenerColor() == 'blanco':
13 self.visitabep(unVertice)
14
15 def visitabep(self,verticeInicio):
16 verticeInicio.asignarColor('gris')
17 self.tiempo += 1
18 verticeInicio.asignarDescubrimiento(self.tiempo)
19 for siguienteVertice in verticeInicio.obtenerConexiones():
20 if siguienteVertice.obtenerColor() == 'blanco':
21 siguienteVertice.asignarPredecesor(verticeInicio)
22 self.visitabep(siguienteVertice)
23 verticeInicio.asignarColor('negro')
24 self.tiempo += 1
25 verticeInicio.asignarFinalizacion(self.tiempo)
Aunque nuestra implementación de bea sólo estaba interesada en considerar nodos para los que había una ruta que llevaba de regreso al inicio, es posible crear un bosque de anchura que represente la ruta más corta entre todas las parejas de nodos en el grafo. Dejamos esto como ejercicio. En nuestros próximos dos algoritmos vamos a ver por qué es importante el seguimiento del árbol de profundidad.
El método visitabep comienza con un solo vértice llamado verticeInicio y explora todos los vértices blancos vecinos lo más profundamente posible. Si usted examina atentamente el código de visitabep y lo compara con la búsqueda en anchura, lo que debería notar es que el algoritmo visitabep es casi idéntico a bea, excepto que en la última línea del ciclo for interno, visitabep se llama a sí misma recursivamente para continuar la búsqueda a un nivel más profundo, mientras que bea añade el nodo a una cola para su exploración posterior. Es interesante observar que donde bea usa una cola, visitabep usa una pila. Usted no verá una pila en el código, pero está implícita en la llamada recursiva a visitabep.
La siguiente secuencia de figuras ilustra en acción el algoritmo de búsqueda en profundidad para un grafo pequeño. En estas figuras, las líneas punteadas indican aristas que están comprobadas, aunque el nodo en el otro extremo de la arista ya se ha añadido al árbol de profundidad. En el código esta prueba se realiza comprobando que el color del otro nodo no sea blanco.
La búsqueda comienza en el vértice A del grafo (Figura 14). Puesto que todos los vértices son blancos al comienzo de la búsqueda, el algoritmo visita el vértice A. El primer paso al visitar un vértice es pintarlo de gris, lo que indica que se está explorando el vértice y al tiempo de descubrimiento se le asigna 1. Dado que el vértice A tiene dos vértices adyacentes (B, D), cada uno de ellos requiere ser visitado también. Tomaremos la decisión arbitraria de que visitaremos los vértices adyacentes en orden alfabético.
El vértice B se visita a continuación (Figura 15), por lo que se pinta de gris y se asigna 2 a su tiempo de descubrimiento. El vértice B también es adyacente a otros dos nodos (C, D), así que seguiremos en orden alfabético y visitaremos a continuación el nodo C.
Visitar el vértice C (Figura 16) nos lleva al final de una rama del árbol. Después de pintar el nodo de gris y asignarle 3 a su tiempo de descubrimiento, el algoritmo también determina que no hay vértices adyacentes a C. Esto significa que hemos terminado de explorar el nodo C y por lo tanto podemos pintar el vértice de negro y asignarle 4 al tiempo final. Usted puede ver el estado de nuestra búsqueda en este punto en la Figura 17.
Dado que el vértice C era el final de una rama, ahora regresamos al vértice B y seguimos explorando los nodos adyacentes a B. El único vértice adicional que se debe explorar desde B es D, por lo que ahora podemos visitar D (Figura 18) y continuar nuestra búsqueda desde el vértice D. El vértice D nos conduce rápidamente al vértice E (Figura 19). El vértice E tiene dos vértices adyacentes, B y F. Normalmente exploraríamos estos vértices adyacentes en orden alfabético, pero como B ya está pintado de gris, el algoritmo reconoce que no debería visitar B, ya que hacerlo pondría al algoritmo en un ciclo. Así, la exploración continúa con el siguiente vértice de la lista, a saber F (Figura 20).
El vértice F tiene sólo un vértice adyacente, C, pero como C está pintado de negro, no hay nada más que explorar, y el algoritmo ha llegado al final de otra rama. De aquí en adelante, verá usted desde la Figura 21 hasta la Figura 25 que el algoritmo regresa al primer nodo, asignando los tiempos de finalización y pintando los vértices de color negro.
Figura 14: Construcción del árbol de búsqueda en profundidad-10¶
Figura 14: Construcción del árbol de búsqueda en profundidad-10
Figura 15: Construcción del árbol de búsqueda en profundidad-11¶
Figura 15: Construcción del árbol de búsqueda en profundidad-11
Figura 16: Construcción del árbol de búsqueda en profundidad-12¶
Figura 16: Construcción del árbol de búsqueda en profundidad-12
Figura 17: Construcción del árbol de búsqueda en profundidad-13¶
Figura 17: Construcción del árbol de búsqueda en profundidad-13
Figura 18: Construcción del árbol de búsqueda en profundidad-14¶
Figura 18: Construcción del árbol de búsqueda en profundidad-14
Figura 19: Construcción del árbol de búsqueda en profundidad-15¶
Figura 19: Construcción del árbol de búsqueda en profundidad-15
Figura 20: Construcción del árbol de búsqueda en profundidad-16¶
Figura 20: Construcción del árbol de búsqueda en profundidad-16
Figura 21: Construcción del árbol de búsqueda en profundidad-17¶
Figura 21: Construcción del árbol de búsqueda en profundidad-17
Figura 22: Construcción del árbol de búsqueda en profundidad-18¶
Figura 22: Construcción del árbol de búsqueda en profundidad-18
Figura 23: Construcción del árbol de búsqueda en profundidad-19¶
Figura 23: Construcción del árbol de búsqueda en profundidad-19
Figura 24: Construcción del árbol de búsqueda en profundidad-20¶
Figura 24: Construcción del árbol de búsqueda en profundidad-20
Figura 25: Construcción del árbol de búsqueda en profundidad-21¶
Figura 25: Construcción del árbol de búsqueda en profundidad-21
Los tiempos de inicio y finalización de cada nodo muestran una propiedad denominada propiedad de paréntesis. Esta propiedad significa que todos los hijos de un nodo en particular en el árbol de profundidad tienen un tiempo de descubrimiento posterior y un tiempo de finalización anterior que aquellos de su padre. La Figura 26 muestra el árbol construido por el algoritmo de búsqueda en profundidad.
Figura 26: TEl árbol resultante de la búsqueda en profundidad¶
Figura 26: TEl árbol resultante de la búsqueda en profundidad