Entiendo las diferencias entre DFS y BFS, pero me interesa saber cuándo es más práctico usar uno sobre el otro.

¿Alguien podría dar algún ejemplo de cómo DFS superaría a BFS y viceversa?

Eso depende en gran medida de la estructura del árbol de búsqueda y del número y ubicación de las soluciones (también conocidos como elementos buscados).

• Si sabe que una solución no está lejos de la raíz del árbol, una primera búsqueda de amplitud (BFS) podría ser mejor.

• Si el árbol es muy profundo y las soluciones son raras, la primera búsqueda profunda (DFS) puede llevar mucho tiempo, pero BFS podría ser más rápido.

• Si el árbol es muy ancho, un BFS podría necesitar demasiada memoria, por lo que podría ser completamente poco práctico.

• Si las soluciones son frecuentes pero ubicadas en lo profundo del árbol, BFS podría no ser práctico.

• Si el árbol de búsqueda es muy profundo, deberá restringir la profundidad de búsqueda para la búsqueda de profundidad primero (DFS), de todos modos (por ejemplo, con profundización iterativa).

Pero estas son solo reglas generales; probablemente necesites experimentar.

Búsqueda de profundidad primero

Las búsquedas de profundidad primero se usan a menudo en simulaciones de juegos (y situaciones similares a juegos en el mundo real). En un juego típico, puedes elegir una de varias acciones posibles. Cada opción conduce a más opciones, cada una de las cuales conduce a más opciones, y así sucesivamente en un gráfico de posibilidades en forma de árbol en constante expansión.

Por ejemplo, en juegos como Ajedrez, tic-tac-toe cuando decides qué movimiento hacer, puedes imaginar mentalmente un movimiento, luego las posibles respuestas de tu oponente, luego tus respuestas, y así sucesivamente. Puede decidir qué hacer al ver qué movimiento conduce al mejor resultado.

Solo algunos caminos en un árbol de juego conducen a tu victoria. Algunos conducen a una victoria de tu oponente, cuando llegas a tal final, debes retroceder o retroceder a un nodo anterior e intentar un camino diferente. De esta manera exploras el árbol hasta que encuentras un camino con una conclusión exitosa. Luego haces el primer movimiento a lo largo de este camino.

Búsqueda de amplitud

La búsqueda de amplitud tiene una propiedad interesante: primero encuentra todos los vértices que están a un borde del punto de partida, luego todos los vértices que están a dos bordes, y así sucesivamente. Esto es útil si está tratando de encontrar la ruta más corta desde el vértice inicial hasta un vértice dado. Comienza un BFS, y cuando encuentra el vértice especificado, sabe que la ruta que ha trazado hasta ahora es la ruta más corta al nodo. Si hubiera un camino más corto, el BFS ya lo habría encontrado.

La búsqueda de amplitud se puede utilizar para encontrar los nodos vecinos en redes de igual a igual como BitTorrent, sistemas GPS para encontrar ubicaciones cercanas, sitios de redes sociales para encontrar personas en la distancia especificada y cosas por el estilo.

Buena explicación de http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/

Un ejemplo de BFS

Aquí hay un ejemplo de cómo se vería un BFS. Esto es algo así como el nivel de árbol de orden transversal, donde usaremos QUEUE con un enfoque ITERATIVO (en su mayoría RECURSION terminará con DFS). Los números representan el orden en el que se accede a los nodos en un BFS:

En una primera búsqueda en profundidad, comienza en la raíz y sigue una de las ramas del árbol lo más lejos posible hasta que encuentre el nodo que está buscando o golpee un nodo hoja (un nodo sin hijos). Si golpea un nodo hoja, entonces continúa la búsqueda del antepasado más cercano con hijos inexplorados.

Un ejemplo de DFS

Aquí hay un ejemplo de cómo se vería un DFS. Creo que el recorrido del orden posterior en el árbol binario comenzará a funcionar desde el nivel Leaf primero. Los números representan el orden en que se accede a los nodos en un DFS:

Diferencias entre DFS y BFS

Comparando BFS y DFS, la gran ventaja de DFS es que tiene requisitos de memoria mucho más bajos que BFS, porque no es necesario almacenar todos los punteros secundarios en cada nivel. Dependiendo de los datos y de lo que esté buscando, DFS o BFS podrían ser ventajosos.

Por ejemplo, dado un árbol genealógico si uno buscara a alguien en el árbol que todavía está vivo, entonces sería seguro asumir que esa persona estaría en la parte inferior del árbol. Esto significa que un BFS tardaría mucho tiempo en alcanzar ese último nivel. Un DFS, sin embargo, encontraría el objetivo más rápido. Pero, si uno buscara a un miembro de la familia que murió hace mucho tiempo, esa persona estaría más cerca de la copa del árbol. Entonces, un BFS generalmente sería más rápido que un DFS. Por lo tanto, las ventajas de cualquiera varían según los datos y lo que está buscando.

Un ejemplo más es Facebook; Sugerencia sobre amigos de amigos. Necesitamos amigos inmediatos para que nos sugieran dónde podemos usar BFS. Puede ser encontrar el camino más corto o detectar el ciclo (usando recursividad) podemos usar DFS.

Breadth First Search es generalmente el mejor enfoque cuando la profundidad del árbol puede variar, y solo necesita buscar una solución en parte del árbol. Por ejemplo, encontrar la ruta más corta desde un valor inicial hasta un valor final es un buen lugar para usar BFS.

La primera búsqueda de profundidad se usa comúnmente cuando necesita buscar en todo el árbol. Es más fácil de implementar (usando recursividad) que BFS, y requiere menos estado: si bien BFS requiere que almacene toda la 'frontera', DFS solo requiere que almacene la lista de nodos principales del elemento actual.

DFS es más eficiente en espacio que BFS, pero puede llegar a profundidades innecesarias.

Sus nombres son reveladores: si hay una gran amplitud (es decir, un gran factor de ramificación), pero una profundidad muy limitada (por ejemplo, un número limitado de "movimientos"), entonces DFS puede ser más preferible que BFS.

En IDDFS

Cabe mencionar que hay una variante menos conocida que combina la eficiencia espacial de DFS, pero (acumulativamente) la visita de orden de nivel de BFS, es la búsqueda iterativa de profundización en profundidad . Este algoritmo vuelve a visitar algunos nodos, pero solo contribuye con un factor constante de diferencia asintótica.

Cuando aborda esta pregunta como programador, se destaca un factor: si está utilizando la recursividad, entonces la búsqueda en profundidad es más sencilla de implementar, ya que no necesita mantener una estructura de datos adicional que contenga los nodos aún por explorar.

Aquí está la búsqueda profunda de un gráfico no orientado si está almacenando información "ya visitada" en los nodos:

def dfs(origin):                               # DFS from origin:
    origin.visited = True                      # Mark the origin as visited
    for neighbor in origin.neighbors:          # Loop over the neighbors
        if not neighbor.visited: dfs(next)     # Visit each neighbor if not already visited

Si almacena información "ya visitada" en una estructura de datos separada:

def dfs(node, visited):                        # DFS from origin, with already-visited set:
    visited.add(node)                          # Mark the origin as visited
    for neighbor in node.neighbors:            # Loop over the neighbors
        if not neighbor in visited:            # If the neighbor hasn't been visited yet,
            dfs(node, visited)                 # then visit the neighbor
dfs(origin, set())

Compare esto con la búsqueda de amplitud en la que necesita mantener una estructura de datos separada para la lista de nodos que aún debe visitar, pase lo que pase.

Una ventaja importante de BFS sería que puede usarse para encontrar la ruta más corta entre dos nodos en un gráfico no ponderado. Mientras que no podemos usar DFS para lo mismo .

Para BFS, podemos considerar el ejemplo de Facebook. Recibimos sugerencias para agregar amigos del perfil de FB de otro perfil de otros amigos. Suponga que A-> B, mientras que B-> E y B-> F, entonces A recibirá sugerencias para E y F. Deben estar usando BFS para leer hasta el segundo nivel. DFS se basa más en escenarios en los que queremos pronosticar algo en función de los datos que tenemos desde el origen hasta el destino. Como ya se mencionó sobre el ajedrez o el sudoku. Una vez que lo que tengo diferente aquí es, creo que DFS debería usarse para la ruta más corta porque DFS cubrirá toda la ruta primero y luego podremos decidir la mejor. Pero como BFS utilizará el enfoque de greedy, podría parecer que es el camino más corto, pero el resultado final puede diferir. Déjame saber si mi comprensión es incorrecta.

Algunos algoritmos dependen de las propiedades particulares de DFS (o BFS) para funcionar. Por ejemplo, el algoritmo Hopcroft y Tarjan para encontrar componentes conectados a 2 aprovecha el hecho de que cada nodo ya visitado por DFS se encuentra en la ruta desde la raíz hasta el nodo explorado actualmente.

La siguiente es una respuesta integral a lo que está preguntando.

En lenguaje sencillo:

El algoritmo Breadth First Search (BFS), a partir de su nombre "Breadth", descubre a todos los vecinos de un nodo a través de los bordes externos del nodo, luego descubre a los vecinos no visitados de los vecinos mencionados anteriormente a través de sus bordes externos y así sucesivamente, hasta que todos se visitan los nodos accesibles desde la fuente original (podemos continuar y tomar otra fuente original si quedan nodos no visitados y así sucesivamente). Es por eso que puede usarse para encontrar la ruta más corta (si hay alguna) desde un nodo (fuente original) a otro nodo si los pesos de los bordes son uniformes.

El algoritmo de búsqueda primero en profundidad (DFS), a partir de su nombre "Profundidad", descubre a los vecinos no visitados del nodo x descubierto más recientemente a través de sus bordes externos. Si no hay un vecino no visitado desde el nodo x, el algoritmo retrocede para descubrir los vecinos no visitados del nodo (a través de sus bordes exteriores) desde los cuales se descubrió el nodo x, y así sucesivamente, hasta que se visiten todos los nodos accesibles desde la fuente original. (podemos continuar y tomar otra fuente original si quedan nodos no visitados y así sucesivamente).

Tanto BFS como DFS pueden estar incompletos. Por ejemplo, si el factor de ramificación de un nodo es infinito, o muy grande para que los recursos (memoria) admitan (por ejemplo, cuando se almacenan los nodos que se descubrirán a continuación), BFS no está completo aunque la clave buscada pueda estar a una distancia de pocos bordes de la fuente original. Este factor de ramificación infinito puede deberse a opciones infinitas (nodos vecinos) de un nodo dado para descubrir. Si la profundidad es infinita, o muy grande para que los recursos (memoria) sean compatibles (por ejemplo, cuando se almacenan los nodos que se descubrirán a continuación), entonces DFS no está completo aunque la clave buscada pueda ser el tercer vecino de la fuente original. Esta profundidad infinita puede deberse a una situación en la que hay, para cada nodo que el algoritmo descubre, al menos una nueva opción (nodo vecino) que no se ha visitado antes.

Por lo tanto, podemos concluir cuándo usar BFS y DFS. Supongamos que estamos tratando con un factor de ramificación limitado manejable y una profundidad limitada manejable. Si el nodo buscado es poco profundo, es decir, accesible después de algunos bordes de la fuente original, entonces es mejor usar BFS. Por otro lado, si el nodo buscado es profundo, es decir, accesible después de muchos bordes desde la fuente original, entonces es mejor usar DFS.

Por ejemplo, en una red social si queremos buscar personas que tengan intereses similares de una persona específica, podemos aplicar BFS de esta persona como fuente original, porque en su mayoría estas personas serán sus amigos directos o amigos de amigos, es decir, uno o dos bordes lejos. Por otro lado, si queremos buscar personas que tengan intereses completamente diferentes de una persona específica, podemos aplicar DFS de esta persona como fuente original, porque en su mayoría estas personas estarán muy lejos de él, es decir, amigo de amigo de amigo. .... es decir, demasiados bordes lejos.

Las aplicaciones de BFS y DFS pueden variar también debido al mecanismo de búsqueda en cada una. Por ejemplo, podemos usar BFS (suponiendo que el factor de ramificación es manejable) o DFS (asumiendo que la profundidad es manejable) cuando solo queremos verificar la accesibilidad de un nodo a otro sin tener información de dónde puede estar ese nodo. Además, ambos pueden resolver las mismas tareas, como la ordenación topológica de un gráfico (si lo tiene). BFS se puede utilizar para encontrar la ruta más corta, con bordes de peso unitario, desde un nodo (fuente original) a otro. Mientras que, DFS puede usarse para agotar todas las opciones debido a su naturaleza de profundizar, como descubrir el camino más largo entre dos nodos en un gráfico acíclico. También DFS, se puede utilizar para la detección de ciclos en un gráfico.

Al final, si tenemos una profundidad infinita y un factor de ramificación infinito, podemos usar la Búsqueda de profundización iterativa (IDS).

De acuerdo con las propiedades de DFS y BFS. Por ejemplo, cuando queremos encontrar el camino más corto. usualmente usamos bfs, puede garantizar el 'más corto'. pero dfs solo puede garantizar que podemos llegar desde este punto, podemos lograr ese punto, no podemos garantizar el 'más corto'.

Creo que depende de qué problemas estés enfrentando.

1. ruta más corta en gráfico simple -> bfs
2. todos los resultados posibles -> dfs
3. buscar en el gráfico (tratar el árbol, martix como un gráfico también) -> dfs ....

Debido a que las búsquedas de profundidad primero utilizan una pila a medida que se procesan los nodos, se proporciona retroceso con DFS. Debido a que Breadth-First Searches utiliza una cola, no una pila, para realizar un seguimiento de los nodos que se procesan, BFS no proporciona retroceso.

Cuando el ancho del árbol es muy grande y la profundidad es baja, use DFS ya que la pila de recursión no se desbordará. Use BFS cuando el ancho es bajo y la profundidad es muy grande para atravesar el árbol.

Este es un buen ejemplo para demostrar que BFS es mejor que DFS en ciertos casos. https://leetcode.com/problems/01-matrix/

Cuando se implementan correctamente, ambas soluciones deben visitar celdas que tengan una distancia mayor que la celda actual +1. Pero DFS es ineficiente y visitó repetidamente la misma celda que resulta en la complejidad O (n * n).

Por ejemplo,

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,

Depende de la situación en la que se use. Siempre que tengamos un problema para atravesar un gráfico, lo hacemos con algún propósito. Cuando hay un problema para encontrar la ruta más corta en un gráfico no ponderado, o para encontrar si un gráfico es bipartito, podemos usar BFS. Para problemas de detección de ciclos o cualquier lógica que requiera retroceso, podemos usar DFS.