Diferencia entre BFS y DFS

Breadth-First Search:
BFS, Breadth-First Search, es una técnica basada en vértices para encontrar la ruta más corta en el gráfico. Utiliza una estructura de datos de cola que sigue primero en entrar, primero en salir. En BFS, se selecciona un vértice a la vez cuando se visita y se marca, luego se visitan sus adyacentes y se almacenan en la cola. Es más lento que DFS. 
Ejemplo :

 Input:
        A
       / \
      B   C
     /   / \
    D   E   F

Producción: 

A, B, C, D, E, F

Búsqueda en primer lugar en profundidad:
DFS, búsqueda en primer lugar en profundidad , es una técnica basada en bordes. Utiliza la estructura de datos Stack y realiza dos etapas: primero, los vértices visitados se insertan en la pila y, en segundo lugar, si no hay vértices, se extraen los vértices visitados. 
Ejemplo: 

  Input:
        A
       / \
      B   D
     /   / \
    C   E   F

Producción: 

A, B, D, C, E, F

BFS frente a DFS

S. No.	Parámetros	BFS	SFD
1.	Representa	BFS significa Breadth First Search.	DFS significa búsqueda en profundidad primero.
2.	Estructura de datos	BFS (búsqueda primero en amplitud) utiliza la estructura de datos de la cola para encontrar la ruta más corta.	DFS (búsqueda primero en profundidad) utiliza la estructura de datos Stack.
3.	Definición	BFS es un enfoque transversal en el que primero recorremos todos los Nodes en el mismo nivel antes de pasar al siguiente nivel.	DFS también es un enfoque transversal en el que el recorrido comienza en el Node raíz y continúa a través de los Nodes en la medida de lo posible hasta llegar al Node sin Nodes cercanos no visitados.
4.	Técnica	BFS se puede usar para encontrar la ruta más corta de una sola fuente en un gráfico no ponderado porque, en BFS, alcanzamos un vértice con un número mínimo de aristas desde un vértice fuente.	En DFS, podríamos atravesar más aristas para llegar a un vértice de destino desde una fuente.
5.	Diferencia conceptual	BFS construye el árbol nivel por nivel.	DFS construye el árbol subárbol por subárbol.
6.	Enfoque utilizado	Funciona con el concepto FIFO (primero en entrar, primero en salir).	Funciona con el concepto LIFO (Last In First Out).
7.	Adecuado para	BFS es más adecuado para buscar vértices más cercanos a la fuente dada.	DFS es más adecuado cuando hay soluciones fuera de la fuente.
8.	Adecuado para Decision Treestheirwinning	BFS considera primero a todos los vecinos y, por lo tanto, no es adecuado para árboles de toma de decisiones utilizados en juegos o rompecabezas.	DFS es más adecuado para problemas de juegos o rompecabezas. Tomamos una decisión y luego exploramos todos los caminos a través de esta decisión. Y si esta decisión conduce a una situación ganadora, nos detenemos.
9.	Complejidad del tiempo	La complejidad de tiempo de BFS es O (V + E) cuando se usa la lista de adyacencia y O (V ^ 2) cuando se usa la array de adyacencia, donde V representa los vértices y E representa los bordes.	La complejidad de tiempo de DFS también es O (V + E) cuando se usa la lista de adyacencia y O (V ^ 2) cuando se usa la array de adyacencia, donde V representa los vértices y E representa los bordes.
10	Visita de hermanos/niños	Aquí se visita a los hermanos antes que a los niños.	Aquí, los niños son visitados antes que los hermanos.
11	Eliminación de Nodes atravesados	Los Nodes que se recorren varias veces se eliminan de la cola.	Los Nodes visitados se agregan a la pila y luego se eliminan cuando no hay más Nodes para visitar.
12	retrocediendo	En BFS no existe el concepto de retroceso.	El algoritmo DFS es un algoritmo recursivo que utiliza la idea de retroceder
13	Aplicaciones	BFS se utiliza en diversas aplicaciones, como gráficos bipartitos, rutas más cortas, etc.	DFS se utiliza en diversas aplicaciones, como gráficos acíclicos y orden topológico, etc.
14	Memoria	BFS requiere más memoria.	DFS requiere menos memoria.
15.	Optimalidad	BFS es óptimo para encontrar el camino más corto.	DFS no es óptimo para encontrar la ruta más corta.
dieciséis.	Complejidad del espacio	En BFS, la complejidad del espacio es más crítica en comparación con la complejidad del tiempo.	DFS tiene una complejidad de espacio menor porque a la vez necesita almacenar solo una ruta desde la raíz hasta el Node hoja.
17	Velocidad	BFS es lento en comparación con DFS.	DFS es rápido en comparación con BFS.
18	¿Cuándo usar?	Cuando el objetivo está cerca de la fuente, BFS funciona mejor.	Cuando el objetivo está lejos de la fuente, es preferible DFS.

Consulte también BFS frente a DFS para árbol binario para conocer las diferencias de un recorrido de árbol binario.