Definición:
Una Búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.
Para recorrer los medios para visitar los vértices en un orden sistemático. Debe estar familiarizado con varios métodos de recorrido de árboles:
preorden: visitar cada nodo antes de sus hijos.
postorden: visitar cada nodo después de sus hijos.
finde (por árboles binarios solamente): subárbol visita a la izquierda, el nodo, subárbol derecho.
Primera profundidad de la búsqueda
La búsqueda en profundidad primero es otra manera de atravesar los gráficos, que está estrechamente relacionado con el recorrido preorden de un árbol. Recordemos que recorrido preorden simplemente visita cada nodo antes de sus hijos. Es muy fácil de programar como una rutina recursiva:
preorden (nodo v)
{
visita (v);
para cada hijo w de v
preorden (w);
}
Para convertir esto en un algoritmo de recorrido gráfico, básicamente reemplazar "niño" por "vecino". Pero para evitar bucles infinitos, sólo quiere visitar una vez cada vértice. Al igual que en BFS podemos utilizar las marcas para hacer un seguimiento de los vértices que ya han sido visitados, y no visitar de nuevo. Además, al igual que en BFS, podemos utilizar esta búsqueda de construir un árbol de expansión con ciertas propiedades útiles.
dfs (vértice v)
{
visita (v);
para cada vecino w de v
si w es no visitados
{
DFS (w);
añadir vw borde de árbol T
}
}
El general algoritmo de profundidad primera búsqueda simplemente inicializa una serie de marcadores para que podamos saber qué vértices son visitados, elige un vértice de partida x, inicializa árbol T a x, y pide dfs (x). Al igual que en la amplitud de la búsqueda en primer lugar, si un vértice tiene varios vecinos, sería igualmente correcto para ir a través de ellos en cualquier orden. No se limitó a decir "para cada vecino no visitados de v" porque es muy importante para retrasar la prueba para saber si un vértice es visitado hasta las llamadas recursivas para los vecinos anteriores terminado.
La prueba de que esto produce un árbol de expansión (el árbol de profundidad primera búsqueda) es esencialmente el mismo que el de BFS, así que no voy a repetir. Sin embargo, mientras el árbol BFS es típicamente "corto y espeso", el árbol DFS suele ser "largo y fibroso".
Al igual que hicimos para BFS, podemos utilizar DFS para clasificar las aristas de G en tipos. Cualquiera de un vw borde está en el árbol DFS sí mismo, v es un antecesor de w, o w es un ancestro de v. (Estos dos últimos casos deben ser considerados como un solo tipo, ya que sólo difieren en qué orden nos fijamos en los vértices pulgadas) Lo que esto significa es que si v y w son diferentes en subárboles de v, no podemos tener una ventaja de v a w. Esto es porque si por ejemplo un borde existido y (dicen) v se visitaron en primer lugar, entonces la única forma que se evite agregar vw al árbol DFS sería si w fueron visitadas durante una de las llamadas recursivas de v, v, pero luego se le un antepasado de w.
Como un ejemplo de por qué esta propiedad puede ser útil, vamos a probar el hecho siguiente: en cualquier grafo G, el G tiene camino de longitud por lo menos k. o G O (kn) bordes.
Prueba: Buscar en la trayectoria más larga en el árbol DFS. Si tiene una longitud de al menos k, hemos terminado. De lo contrario, ya que cada arista conecta un antepasado y un descendiente, podemos limitan el número de aristas, contando el número total de los antepasados de cada descendiente, pero si el camino más largo es más corto que k, tiene cada descendiente en la mayoría de k-1 antepasados. Por lo tanto no puede haber más en los bordes (k-1) n.
Este hecho puede ser utilizado como parte de un algoritmo para encontrar las rutas de largo en G, otro problema isomorfismo subgrafo estrechamente relacionado con el problema del vendedor ambulante. Si k es una constante pequeña (como por ejemplo 5) se pueden encontrar caminos de longitud k en un tiempo lineal (medida en función de n). Sin embargo, medido en función de k, el tiempo es exponencial, lo que no es de extrañar porque este problema está estrechamente relacionado con el problema del vendedor ambulante. Para más información sobre este problema en particular, ver a Michael R. Fellows y Michael A. Langston, "En la búsqueda, de decisiones y la eficiencia de los algoritmos de tiempo polinómico", 21 Symp del ACM. Teoría de la Computación, 1989, pp 501-512.
Relación entre BFS y DFS
Puede que no sea claro en el pseudo-código anterior, pero BFS y DFS están estrechamente relacionados entre sí. (De hecho en la clase he tratado de describir una búsqueda en la que he modificado el "añadir al final de la lista" línea en el pseudocódigo BFS "añadir al principio de la lista", pero el algoritmo de recorrido resultante no era la misma DFS).
Con un poco de cuidado se puede hacer BFS y DFS parecen casi lo mismo que los demás (lo más parecido, por ejemplo, Prim y los algoritmos de Dijkstra son entre sí):
BFS (G)
{
lista L = vacío
T = árbol vacío
elegir un vértice de partida x
búsqueda (x)
al mismo tiempo (no vacío L)
quitar el borde (v, w) desde el inicio de la L
si no w visitado aún
{
añadir (v, w) a T
búsqueda (w)
}
}
DFS (G)
{
lista L = vacío
T = árbol vacío
elegir un vértice de partida x
búsqueda (x)
al mismo tiempo (no vacío L)
quitar el borde (v, w) del extremo de la L
si no w visitado aún
{
añadir (v, w) a T
búsqueda (w)
}
}
búsqueda (vértice v)
{
visita (v);
para cada arista (v, w)
agregar borde (v, w) al final de la L
}
Ambos algoritmos de búsqueda ahora mantener una lista de los bordes para explorar, la única diferencia entre ambos es que, si bien ambos algoritmos añade elementos al final de L, BFS los elimina desde el principio, lo que resulta en el mantenimiento de la lista como una cola , mientras que DFS las aleja de la final, el mantenimiento de la lista como una pila.
BFS y DFS en grafos dirigidos
Aunque hemos discutido para grafos no dirigidos, las rutinas misma búsqueda de trabajo sin modificar esencialmente para grafos dirigidos. La única diferencia es que cuando la exploración de un vértice v, que sólo quiere ver en los bordes (v, w) de salir de v; ignoramos los bordes que entra a v.
Para grafos dirigidos, también, podemos probar las propiedades de Niza de la BFS y el árbol DFS que ayudan a clasificar a los bordes de la gráfica. Para BFS en grafos dirigidos, cada borde de la gráfica o conecta dos vértices en el mismo nivel, se pone exactamente un nivel, o va a cualquier número de niveles. Para DFS, cada borde o conecta un antepasado a un descendiente, un descendiente de un antepasado, o un nodo a un nodo en un árbol visitado. No es posible obtener "los bordes hacia adelante" que conecta un nodo a un subárbol visitó antes de ese nodo.Vamos a utilizar esta propiedad la próxima vez para comprobar si un grafo dirigido es fuertemente conectados (cada vértice puede llegar a cualquier otro).
La búsqueda en profundidad primero es otra manera de atravesar los gráficos, que está estrechamente relacionado con el recorrido preorden de un árbol. Recordemos que recorrido preorden simplemente visita cada nodo antes de sus hijos. Es muy fácil de programar como una rutina recursiva:
preorden (nodo v)
{
visita (v);
para cada hijo w de v
preorden (w);
}
Para convertir esto en un algoritmo de recorrido gráfico, básicamente reemplazar "niño" por "vecino". Pero para evitar bucles infinitos, sólo quiere visitar una vez cada vértice. Al igual que en BFS podemos utilizar las marcas para hacer un seguimiento de los vértices que ya han sido visitados, y no visitar de nuevo. Además, al igual que en BFS, podemos utilizar esta búsqueda de construir un árbol de expansión con ciertas propiedades útiles.
dfs (vértice v)
{
visita (v);
para cada vecino w de v
si w es no visitados
{
DFS (w);
añadir vw borde de árbol T
}
}
El general algoritmo de profundidad primera búsqueda simplemente inicializa una serie de marcadores para que podamos saber qué vértices son visitados, elige un vértice de partida x, inicializa árbol T a x, y pide dfs (x). Al igual que en la amplitud de la búsqueda en primer lugar, si un vértice tiene varios vecinos, sería igualmente correcto para ir a través de ellos en cualquier orden. No se limitó a decir "para cada vecino no visitados de v" porque es muy importante para retrasar la prueba para saber si un vértice es visitado hasta las llamadas recursivas para los vecinos anteriores terminado.
La prueba de que esto produce un árbol de expansión (el árbol de profundidad primera búsqueda) es esencialmente el mismo que el de BFS, así que no voy a repetir. Sin embargo, mientras el árbol BFS es típicamente "corto y espeso", el árbol DFS suele ser "largo y fibroso".
Al igual que hicimos para BFS, podemos utilizar DFS para clasificar las aristas de G en tipos. Cualquiera de un vw borde está en el árbol DFS sí mismo, v es un antecesor de w, o w es un ancestro de v. (Estos dos últimos casos deben ser considerados como un solo tipo, ya que sólo difieren en qué orden nos fijamos en los vértices pulgadas) Lo que esto significa es que si v y w son diferentes en subárboles de v, no podemos tener una ventaja de v a w. Esto es porque si por ejemplo un borde existido y (dicen) v se visitaron en primer lugar, entonces la única forma que se evite agregar vw al árbol DFS sería si w fueron visitadas durante una de las llamadas recursivas de v, v, pero luego se le un antepasado de w.
Como un ejemplo de por qué esta propiedad puede ser útil, vamos a probar el hecho siguiente: en cualquier grafo G, el G tiene camino de longitud por lo menos k. o G O (kn) bordes.
Prueba: Buscar en la trayectoria más larga en el árbol DFS. Si tiene una longitud de al menos k, hemos terminado. De lo contrario, ya que cada arista conecta un antepasado y un descendiente, podemos limitan el número de aristas, contando el número total de los antepasados de cada descendiente, pero si el camino más largo es más corto que k, tiene cada descendiente en la mayoría de k-1 antepasados. Por lo tanto no puede haber más en los bordes (k-1) n.
Este hecho puede ser utilizado como parte de un algoritmo para encontrar las rutas de largo en G, otro problema isomorfismo subgrafo estrechamente relacionado con el problema del vendedor ambulante. Si k es una constante pequeña (como por ejemplo 5) se pueden encontrar caminos de longitud k en un tiempo lineal (medida en función de n). Sin embargo, medido en función de k, el tiempo es exponencial, lo que no es de extrañar porque este problema está estrechamente relacionado con el problema del vendedor ambulante. Para más información sobre este problema en particular, ver a Michael R. Fellows y Michael A. Langston, "En la búsqueda, de decisiones y la eficiencia de los algoritmos de tiempo polinómico", 21 Symp del ACM. Teoría de la Computación, 1989, pp 501-512.
Relación entre BFS y DFS
Puede que no sea claro en el pseudo-código anterior, pero BFS y DFS están estrechamente relacionados entre sí. (De hecho en la clase he tratado de describir una búsqueda en la que he modificado el "añadir al final de la lista" línea en el pseudocódigo BFS "añadir al principio de la lista", pero el algoritmo de recorrido resultante no era la misma DFS).
Con un poco de cuidado se puede hacer BFS y DFS parecen casi lo mismo que los demás (lo más parecido, por ejemplo, Prim y los algoritmos de Dijkstra son entre sí):
BFS (G)
{
lista L = vacío
T = árbol vacío
elegir un vértice de partida x
búsqueda (x)
al mismo tiempo (no vacío L)
quitar el borde (v, w) desde el inicio de la L
si no w visitado aún
{
añadir (v, w) a T
búsqueda (w)
}
}
DFS (G)
{
lista L = vacío
T = árbol vacío
elegir un vértice de partida x
búsqueda (x)
al mismo tiempo (no vacío L)
quitar el borde (v, w) del extremo de la L
si no w visitado aún
{
añadir (v, w) a T
búsqueda (w)
}
}
búsqueda (vértice v)
{
visita (v);
para cada arista (v, w)
agregar borde (v, w) al final de la L
}
Ambos algoritmos de búsqueda ahora mantener una lista de los bordes para explorar, la única diferencia entre ambos es que, si bien ambos algoritmos añade elementos al final de L, BFS los elimina desde el principio, lo que resulta en el mantenimiento de la lista como una cola , mientras que DFS las aleja de la final, el mantenimiento de la lista como una pila.
BFS y DFS en grafos dirigidos
Aunque hemos discutido para grafos no dirigidos, las rutinas misma búsqueda de trabajo sin modificar esencialmente para grafos dirigidos. La única diferencia es que cuando la exploración de un vértice v, que sólo quiere ver en los bordes (v, w) de salir de v; ignoramos los bordes que entra a v.
Para grafos dirigidos, también, podemos probar las propiedades de Niza de la BFS y el árbol DFS que ayudan a clasificar a los bordes de la gráfica. Para BFS en grafos dirigidos, cada borde de la gráfica o conecta dos vértices en el mismo nivel, se pone exactamente un nivel, o va a cualquier número de niveles. Para DFS, cada borde o conecta un antepasado a un descendiente, un descendiente de un antepasado, o un nodo a un nodo en un árbol visitado. No es posible obtener "los bordes hacia adelante" que conecta un nodo a un subárbol visitó antes de ese nodo.Vamos a utilizar esta propiedad la próxima vez para comprobar si un grafo dirigido es fuertemente conectados (cada vértice puede llegar a cualquier otro).
Referencia:
ICS 161 - Departamento de Información y Ciencias de la Computación - UC Irvine
Última actualización: 07 de mayo de 2004, 15:27:14 CEST
No hay comentarios:
Publicar un comentario