Ventaja de la profundidad de la primera búsqueda a través de la anchura de la primera búsqueda o viceversa

Question

He estudiado los algoritmos de cruce de dos gráficos, la profundidad de la primera búsqueda y la primera búsqueda de amplitud. Como ambos algoritmos se utilizan para resolver el mismo problema de cruce de gráficos, me gustaría saber cómo elegir entre los dos. Me refiero a uno más eficiente que el otro o cualquier otra razón por la que elegiría uno sobre el otro en un escenario particular?

Gracias

Answer 1

La principal diferencia para mí es algo teórica. Si tuviera un gráfico de tamaño infinito, DFS nunca encontraría un elemento si existe fuera de la primera ruta que elija. Básicamente seguiría por el primer camino y nunca encontraría el elemento. El BFS finalmente encontraría el elemento.

Si el tamaño del gráfico es finito, es probable que el DFS encuentre un elemento atípico (mayor distancia entre la raíz y el objetivo) más rápido donde BFS encontraría un elemento más cercano más rápido. Excepto en el caso donde DFS elige la ruta del elemento superficial.

Answer 2

En general, BFS es mejor para los problemas relacionados con la búsqueda de las rutas más cortas o problemas algo relacionados. Porque aquí se pasa de un nodo a todos los nodos adyacentes y, por lo tanto, se pasa efectivamente de la longitud de ruta uno a la longitud de ruta dos, y así sucesivamente.

Mientras que DFS en el otro extremo ayuda más en problemas de conectividad y también en encontrar ciclos en el gráfico (aunque creo que es posible que pueda encontrar ciclos con un poco de modificación de BFS también). Determinar la conectividad con DFS es trivial, si llama al procedimiento de exploración dos veces desde el procedimiento DFS, entonces el gráfico está desconectado (esto es para un gráfico no dirigido). Aquí puede ver el algoritmo de componente fuertemente conectado para un gráfico dirigido, que es una modificación de DFS. Otra aplicación del DFS es la clasificación topológica.

Estas son algunas aplicaciones, tanto de los algoritmos:

DFS:

Conectividad
componente fuertemente conexo
topológica Clasificación

BFS:

ruta más corta (Dijkstra es lo que algunos de una modificación de BFS).
Comprobando si el gráfico es Bipartitie.

Answer 3

Para un árbol completo/perfecto, DFS ocupa una cantidad lineal de espacio con respecto a la profundidad del árbol, mientras que BFS ocupa una cantidad exponencial de espacio con respecto a la profundidad del árbol. Esto se debe a que para BFS, la cantidad máxima de nodos en la cola es proporcional a la cantidad de nodos en un nivel del árbol. En DFS, la cantidad máxima de nodos en la pila es proporcional a la profundidad del árbol.

Answer 4

Al atravesar un gráfico con múltiples conexiones, el orden en que se atraviesan los nodos puede influir en gran medida (en muchos órdenes de magnitud) en el número de nodos que se seguirán por el método de desplazamiento. Algún tipo de algoritmo será mucho mejor cuando se usa el ancho primero; otros serán masivamente mejores cuando usen la búsqueda de profundidad.

En un extremo, hacer una búsqueda en profundidad en un árbol binario con N nodos de hoja requiere que el método de desplazamiento realice un seguimiento de nodos lgN mientras que una búsqueda amplia requerirá realizar un seguimiento de al menos N/2 nodos (ya que podría escanear todos los demás nodos antes de escanear cualquier nodo hoja, inmediatamente antes de escanear el primer nodo hoja, se habría encontrado con N/2 de los nodos padre de las hojas que deben rastrearse por separado ya que ninguno de ellos se referencia entre sí) .

En el otro extremo, haciendo un relleno de inundación en una cuadrícula NxN con un método que, si su píxel no se ha coloreado aún, colorea ese píxel y luego inunda a sus vecinos requerirá poner en O (N) coordenadas de píxel si se usa la búsqueda de amplitud, pero O (N^2) coordenadas de píxel si se usa profundidad-primero. Cuando se utiliza la búsqueda de amplitud, la pintura parece "extenderse", independientemente de la forma que se va a pintar; cuando se usa un algoritmo de profundidad para pintar una espiral rectangular, cada línea recta en un lado y dentada en el otro (los lados deben ser rectos y dentados depende del algoritmo exacto utilizado), todas las secciones rectas se pintarán antes de cualquiera de los irregulares, lo que significa que el sistema debe rastrear la ubicación de cada jalón por separado.

Answer 5

En algunos idiomas, un BFS es un poco mejor elección porque lo más sencilla implementación de DFS es recursivo, que introduce una sobrecarga, y también podría hacer que su código para golpear el límite de tamaño de pila para grandes gráficos. La ventaja obvia (y la aplicación) de BFS es que en gráficos no ponderados se puede usar para construir una ruta más corta de u a v. Esto tiene numerosas aplicaciones - por ejemplo, puede calcular el menor número de movimientos necesario para resolver un determinado rompecabezas ejecutando un BFS en su espacio de estado. BFS incluso puede darle las distancias más cortas desde un vértice u a todos los demás vértices en el gráfico: para cada vértice , simplemente recuerde el borde que se usó para descubrirlo.