¿Cuál es la diferencia entre profundidad-primera-búsqueda y amplitud-primera-búsqueda? ¿Por qué DFS visita el nodo después de eliminarlo de una pila mientras que BFS visita el nodo antes de agregarlo a la cola?

BFS visitaría los nodos en el orden que se asemeja más o menos a qué distancia están del vértice inicial.

“Desde la raíz” en el caso del árbol.

Si todos los bordes tienen el mismo peso, el orden de los vértices de visita sería estrictamente “en orden no decreciente de la distancia desde el vértice inicial”.

DFS terminaría completamente una rama antes de comenzar otra.

---

El orden de lo que en realidad se considera una “visita” puede ser algo complicado.

---

Técnicamente, con DFS, hay pedidos anticipados, en orden y posteriores. En orden no tiene mucho sentido para los árboles no binarios; para árboles binarios, sin embargo, tiene propiedades interesantes, más notablemente, produciendo un orden lexicográfico para árboles de búsqueda binarios.

(Reflexione sobre este hecho por un segundo. Si todos los valores en el subárbol izquierdo de cualquier nodo son <= el valor del nodo y todos los valores del subárbol derecho son> el valor de cualquier nodo, entonces en orden genera un lexicográfico transversal del árbol. Eso es casi exactamente para lo que se ha “creado” en orden).

---

Con BFS, en teoría, uno puede tratar de definir “visitar” un nodo como el evento de que ingrese a una cola o como el evento de que abandone la cola.

En realidad, estas dos órdenes serían las mismas, ya que, por definición, la cola es una estructura de datos primero en entrar, primero en salir.

---

Dejando de lado las diferencias entre pre-orden, en orden y post-orden, la diferencia entre DFS y BFS es que DFS va primero a “profundidad” mientras que BFS captura primero la “amplitud”.

---

Para dibujar una analogía simple, imagine recorrer una jerarquía de archivos y carpetas.

BFS primero enumeraría los archivos en la carpeta raíz, luego los archivos un nivel más profundo, luego iría más lejos. Si detiene un BFS desde el principio, obtendrá un corte de “nivel de profundidad”.

DFS entraría en un directorio y lo completaría al 100% antes de salir. Si detiene un DFS desde el principio, lo más probable es que haya pasado la mayor parte de su tiempo en un directorio de nivel superior profundamente anidado y no haya tenido la oportunidad de explorar otros directorios, relativamente no profundos.

---

¿Por qué se usa DFS a menudo?

a) Es más intuitivo para alguien que entiende la recursividad.
b) Es mejor localmente.

Para entender b), reflexione sobre el hecho de que cada directorio de nivel intermedio solo se ingresará una vez y se dejará una vez.

Por lo tanto, si se requiere algún trabajo adicional para ingresar / salir del directorio, DFS minimiza la sobrecarga.

¿Por qué se usa BFS?

Intuitivamente, porque a menudo es un desperdicio mirar en lo profundo de un lugar, mientras que la respuesta puede estar allí, en otra rama, que DFS alcanzaría mucho más tarde.

Como sabe, DFS y BFS tienen diferentes propósitos, se utilizan para visitar los nodos de un gráfico de diferentes maneras. El algoritmo solo describe una forma de lograr esto. Por lo tanto, si marcara un nodo visited cada vez que lo insertara en la pila, su orden de visitar los nodos no cumpliría con la idea de una Búsqueda en profundidad primero (una comprensión intuitiva: debe visitar la profundidad antes de la amplitud)
Veamos la diferencia aplicando el algoritmo provisto en Wikipedia

  procedimiento DFS-iterativo (G, v): 
     deja que S sea una pila 
     S.push (v) 
     mientras que S no está vacío 
         v ← S.pop ()  
         si v no está etiquetado como descubierto: 
             etiqueta v como descubierta  
             para todos los bordes de v a w en G.ad adyacentesEdges (v) do 
                 S.push (w)

a este gráfico
(ese último nodo es ‘F’)

El orden de visita DFS correcto es ABDFECG (si se presiona de derecha a izquierda)
que es lo que obtendrás del algoritmo dado.

pero si visit before pushing , es decir, si usa este algoritmo:

  procedimiento DFS-iterativo (G, v): 
     deja que S sea una pila 
     etiqueta v como descubierta
     S.push (v) 
     mientras que S no está vacío 
         v ← S.pop ()  
             para todos los bordes de v a w en G.ad adyacentesEdges (v) do 
                 si w no está etiquetado como descubierto: 
                     etiqueta w como descubierta  
                     S.push (w)

entonces el pedido que obtendrá es ACBDEFG que no es ni DFS ni BFS .

Si en el algoritmo anterior, en lugar de una Pila, usa una Que, obtendrá un algoritmo BFS adecuado. que te dará ACBGEDF . ¡Pruébalo!
(En BFS, si marca los nodos visited cuando salen de la Que o cuando ingresan, no tiene ningún impacto en el orden, es solo que convencionalmente las personas lo marcan antes de ingresar la Que)

PD: ¡Podría estar equivocado con mis carreras en seco, si encuentra algún error, no dude en sugerir cambios!

Estuviste despierto hasta las 4 de la mañana y es fin de semana, así que te despertaste a las 2 de la tarde y ahora estás atrapado viendo videos de Jake y Amir en YouTube.

El video actual tiene un conjunto de “Recomendar videos” en la barra lateral.

Algunas de estas recomendaciones son videos que desea ver.

Llamemos a estas recomendaciones que desea ver los “vecinos” de su video actual. Forman parte de un conjunto completo de videos que desea ver.

Mientras mira su video actual, se da cuenta de que también quiere ver los videos vecinos X.

Así que haz clic derecho sobre ellos y presiona “Abrir enlace en una pestaña nueva”.

Ahora a la derecha de su video actual, tiene una lista de otros videos para ver, todos en pestañas separadas.

¿Qué vas a hacer después?

Profundidad-Primera búsqueda:

1. Termina de ver su video, luego cierra esta pestaña.
2. Abre la pestaña más a la derecha / última (la pestaña más recientemente agregada).
3. Si ya ha visto ese video hoy, cierre esa pestaña sin abrir ningún vecino.
4. Si no lo ha visto hoy, mire y abra cualquier video recomendado que le interese.

Continúe hasta que todas las pestañas estén cerradas.

Así es como se ve el pedido …

Breadth-First Search:

1. Termina de ver su video, luego cierra esta pestaña.
2. Abre la pestaña más a la izquierda (la primera / más antigua pestaña que abrió).
3. Si ya ha visto ese video hoy, cierre esa pestaña sin abrir ningún vecino.
4. Si no lo ha visto hoy, mire y abra cualquier video recomendado que le interese.

Continúe hasta que todas las pestañas estén cerradas.

Así es como se ve el pedido:

---

La única diferencia en la operación es qué lado usan las búsquedas para elegir la siguiente pestaña:

• La pestaña agregada más recientemente (DFS)
• O la pestaña agregada más antigua (BFS)

En realidad, esto tiene un gran impacto en la cantidad de pestañas que están abiertas en un momento dado, como veremos en breve. Pero primero, para ser claros …

Obtener la pestaña agregada más recientemente primero (DFS) se llama usando una pila:

Obtener la pestaña agregada más antigua primero (BFS) se llama usando una cola:

Con una pila / DFS, solo necesitamos hacer un seguimiento de unos pocos elementos a la vez.

Echemos un vistazo a la cantidad de elementos que necesitamos para realizar un seguimiento de algunos pasos:

Como puede ver … el número promedio de videos que necesitamos hacer un seguimiento en un momento dado es solo:

# Promedio de vecinos para cualquier video * Profundidad del gráfico

El número de videos que necesitamos rastrear es directamente proporcional a la profundidad del gráfico.

Uno mas:

Pero no es así con Breadth-First Search.

Simplemente cambiando de una Pila a una Cola, de repente necesitamos hacer un seguimiento de todos los vecinos de todos los videos en la cola:

Si me salteo algunos pasos, puede ver cómo puede aumentar la cantidad de videos en la cola:

---

Entonces, en BFS, al usar una Cola, el número de videos que debemos seguir puede crecer exponencialmente .

El número promedio de videos que necesitamos hacer un seguimiento en cualquier punto dado se convierte en:

Profundidad del gráfico ^ (número promedio de vecinos)

En lugar de multiplicar los dos, estamos elevando la profundidad a un poder . Entonces, esencialmente el número de elementos rastreados puede ser exponencial.

Puede pensar en esto como el número de pestañas abiertas: con DFS, solo tendrá un puñado de pestañas abiertas en un momento dado, con BFS podría tener un número ridículamente grande.

Es esto (DFS):

vs. esto (BFS):

Como resultado, a pesar de que hacen lo mismo, la Búsqueda en profundidad requiere mucho menos espacio que la Búsqueda en profundidad.

Entonces, si está buscando un gráfico muy grande y tiene un espacio limitado, un DFS a menudo es útil.

Por ejemplo, si usa Recursion, debe mantener todos los videos en la Memoria de pila, que no tiene mucho espacio.

Por lo tanto, generalmente se prefiere usar DFS en esos casos.

---

Pero, como habrás notado, BFS garantiza un pedido específico.

A saber: los elementos más cercanos al inicio son siempre los primeros elementos visitados.

Los elementos más lejanos son los últimos elementos visitados.

DFS no tiene este orden: algunos videos muy alejados del origen tienen números pequeños y otros tienen números grandes.

Entonces, si está buscando determinar cuál es la distancia más corta entre dos elementos, generalmente usará BFS, porque conserva automáticamente esa distancia en el orden en que visita las cosas.

---

Toma un poco de tiempo entenderlo, pero espero que esto te dé una idea de algunos de los pros y los contras de BFS vs DFS y por qué funcionan.

La búsqueda de amplitud primero (BFS) y la búsqueda de profundidad profunda (DFS) son en realidad las mismas, aparte de la estructura de datos utilizada para almacenar los vértices descubiertos.

Un BFS mantiene una cola de vértices que se han descubierto y que aún no se han visitado, y luego visita repetidamente el vértice frontal de la cola, descubriendo a todos sus vecinos y agregándolos al final de la cola. Esto significa que cuanto antes se descubre un vértice, antes se visita, lo que da la forma de “amplitud primero” de la búsqueda.

Un DFS simplemente reemplaza la cola del BFS con una pila, de modo que los vértices recién descubiertos se visitan de inmediato, y los vértices descubiertos hace más tiempo solo se devuelven una vez que se han visitado los nuevos vértices. Esto hace que la búsqueda se “sumerja” hasta el final de la primera ruta de búsqueda antes de considerar cualquier otro vértice.

Entonces, BFS y DFS son en realidad el mismo algoritmo, parametrizado por la estructura interna de datos.

DFS, como su nombre lo indica, es la primera búsqueda en profundidad, comenzará a buscar desde el nodo raíz. Para cada nodo, busca hasta la hoja de ese nodo y marca todos los nodos visitados como verdaderos. Para hacer esto usa stack. Una vez que se encuentra el nodo hoja, comienza a extraer los elementos.
En el caso de BFS, comienza su búsqueda desde el nivel. En otras palabras, también se llama como transversal de orden de nivel. Una vez más, aquí también utilizamos una matriz de nodo visitado para realizar un seguimiento de si el nodo se visita. Una vez que comenzamos el recorrido, empujamos todos los nodos conectados desde la raíz para hacer cola y comenzar nuestro recorrido.

Ahora, llegando al segundo punto de verificación demorada en DFS, se llama así porque en el caso de DFS primero empujamos los nodos de encuentro hasta obtener un nodo hoja. Una vez que obtenemos la hoja, comenzamos a aparecer y verificamos si está visitada o no.

La primera búsqueda de amplitud es como ondas en un estanque. Comienzas un punto y expandes uniformemente tu búsqueda hacia afuera. La primera búsqueda en profundidad es cómo iteraría a través de un árbol.

La primera búsqueda en profundidad se ve así. Primero colocamos 1 en la pila y lo marcamos como usado. Luego salimos de la parte superior de la pila (1) y miramos a sus hijos. Verificamos si se habían agregado previamente, agregamos 8,7,2 a la pila, los marcamos como visitados y regresamos. Entonces nuestra pila se ve así 2,7,8. Luego salimos (2) y examinamos a sus hijos. Entonces agregamos 6, 3 a la pila. Ahora la pila se parece a 3,6,7,8 …
En cada caso estamos agregando nuevos nodos al comienzo de nuestra “cola”.
Página en wikimedia.org

La primera búsqueda de amplitud se ve así: Primero colocamos 1 en la cola a un costo cero. Luego sacamos 1 de la cola, lo marcamos como usado y agregamos sus hijos a un costo cero más el costo de viajar desde 1. Luego examinamos el nodo de menor costo en la cola. La razón por la que no marcamos un nodo como se usa antes de sacarlo de la cola es que a menudo hay muchas formas de llegar a un nodo, y queremos procesar los nodos en el orden de menor costo de ruta al nodo inicial (piense en Dijkstra )
Página en wikimedia.org

Si desea hacer una primera búsqueda amplia en la que solo está contando arcos sin costo, entonces puede marcar un nodo como visitado cuando lo agrega a la cola porque tiene la garantía de agregar todos los nodos a la cola en el orden Desea procesarlos.

(Editar: no estoy seguro de por qué las imágenes no se insertan correctamente)

DFS (Profund First Search) y BFS (Breadth First Search) son algoritmos de búsqueda utilizados para gráficos y árboles. Cuando tiene un árbol o gráfico ordenado, como un BST, es bastante fácil buscar en la estructura de datos para encontrar el nodo que desea. Pero, cuando se le da un árbol o gráfico desordenado, los algoritmos de búsqueda BFS y DFS pueden ser útiles para encontrar lo que está buscando. La decisión de elegir uno sobre el otro debe basarse en el tipo de datos con los que se trata.

En una primera búsqueda de amplitud, comienza en el nodo raíz y luego escanea cada nodo en el primer nivel comenzando desde el nodo más a la izquierda, moviéndose hacia la derecha. Luego continúa escaneando el segundo nivel (comenzando desde la izquierda) y el tercer nivel, y así sucesivamente hasta que haya escaneado todos los nodos, o hasta que encuentre el nodo real que estaba buscando. En un BFS, al atravesar un nivel, necesitamos alguna forma de saber qué nodos atravesar una vez que lleguemos al siguiente nivel. La forma en que se hace esto es almacenando los punteros en los nodos secundarios de un nivel mientras se busca ese nivel. Los punteros se almacenan en la cola FIFO (primero en entrar, primero en salir). Esto, a su vez, significa que BFS usa una gran cantidad de memoria porque tenemos que almacenar los punteros.

Como su nombre lo indica, una búsqueda de amplitud que comienza en el vértice [matemática] v [/ matemática] primero visitará cada vértice [matemática] w [/ matemática] adyacente a [matemática] v [/ matemática], y luego vaya para realizar una búsqueda de amplitud para cada uno de estos [math] w [/ math]. La búsqueda finaliza cuando no se pueden visitar más vértices no visitados de esta manera.

Una búsqueda de profundidad primero que comienza en el vértice [math] v [/ math] primero visitará el primer vértice [math] w [/ math] que está adyacente a [math] v [/ math], y luego realizará una amplitud de búsqueda de este [math] w [/ math]. Cuando esta búsqueda finalmente termine, la búsqueda de profundidad primero visitará el siguiente vértice adyacente a [math] v [/ math]. La búsqueda que comienza en el vértice [math] v [/ math] finaliza cuando se ha realizado una búsqueda para todos los vértices adyacentes a [math] v [/ math].

Echa un vistazo a las animaciones Breadth First Search / Depth First Search.

BFS es más lento que DFS. DFS es más rápido que BFS. BFS requiere más memoria en comparación con DFS. DFS requiere menos memoria en comparación con BFS.
utilizar
BFS es útil para encontrar la ruta más corta. BFS se puede utilizar para encontrar la distancia más corta entre algún nodo inicial y los nodos restantes del gráfico.
DFS no es tan útil para encontrar el camino más corto. Se utiliza para realizar un recorrido de un gráfico general y la idea de DFS es hacer un camino el mayor tiempo posible y luego retroceder ( retroceder ) para agregar ramas también el mayor tiempo posible.

Obsesivo vs maníaco.

Estas búsquedas se aplican a los árboles con raíz, subraíces y nodos de hoja.

La primera búsqueda de amplitud comienza desde el movimiento raíz al siguiente nivel, busca todas las subraíces (tal vez las hojas) y luego pasa al siguiente nivel del árbol y así sucesivamente hasta que se completa la búsqueda en los nodos de hoja

La primera búsqueda en profundidad comienza desde la raíz, se mueve a su primera raíz secundaria izquierda y continuará hasta que se busque el último nodo de la hoja izquierda. Luego, el puntero se mueve nuevamente a la raíz y la búsqueda comienza nuevamente desde la siguiente subraíz de la raíz

Creo que en el caso de DFS, comienzas con un nodo y visitas a uno de sus vecinos no visitados y continúas con eso hasta que no encuentras vecinos. Es decir, empuja todo dentro de la pila sin ninguna marca (marca). Y si no hay ningún vecino, se detiene y hace estallar la parte superior de la pila, ahora lo marca (o al contrario, verifíquelo). a medida que se verifica el vértice, se saca de la pila (no antes).

Pero en el caso de BFS, comienza con un nodo, verifíquelo (márquelo) y luego presione todos sus vecinos no visitados.

DFS: Marque (marque) solo después del pop.
BFS: Verifique al principio.

Creo que esto es lo que significaba allí. No dude en corregirme si me equivoco.

Los voy a diferenciar en función de sus aplicaciones. Usando un bfs es fácil encontrar la ruta más corta desde un nodo dado a cualquier otro nodo … es decir, forma la base para el camino de la ruta más corta.
Si bien dfs puede verificar fácilmente las diferentes propiedades de un gráfico … si ahora lo que significa un borde posterior, borde delantero, borde transversal significa, no sabrá lo que quiero decir …
Básicamente, ambos visitan el gráfico … cuándo usar qué búsqueda depende básicamente de la pregunta … por ejemplo, si queremos probar si un gráfico está conectado individualmente o no, una búsqueda de dfs lo hace fácilmente … mientras dije antes si queremos saber la distancia más corta que una búsqueda bfs lo hace fácilmente.

1.DFS requiere menos memoria ya que tiene que mantener un registro de solo su nodo actual en la ruta, pero en BFS hay almacenamiento de todo el árbol que se ha generado
2.DFS funciona en la pila donde BFS funciona en la cola.
3.DFS se detiene cuando se encuentra uno de ellos.

1.BFS significa amplitud de la primera búsqueda comúnmente utilizada en Queue y DFS significa profundidad de la primera búsqueda

2.BFS se usa para encontrar la ruta más corta, mientras que DFS no se puede usar para encontrarla

3.BFS es más lento que DFS mientras

DFS es más rápido que BFS.

4.BFS requiere más memoria en comparación con DFS mientras

DFS

1. Un BFS busca todas las soluciones en un gráfico para expandir sus nodos; un DFS excava profundamente dentro de un nodo hijo hasta que se alcanza una meta.
2. Las características de un BFS son la complejidad del espacio y el tiempo, la integridad, la prueba de integridad y la optimización; La salida más natural para un DFS es un árbol de expansión con tres clases: bordes delanteros, bordes posteriores y bordes cruzados.

Anchura Primero vs Profundidad Primero

El enlace de arriba explica el concepto maravillosamente. Echa un vistazo.

smjh ni i koi smjhady dfs y bfs