Breadth First Search
BFS significa Breadth First Search es una técnica basada en vértices para encontrar el camino más corto en un gráfico. Utiliza una estructura de datos de cola que sigue al primero que entra es el primero que sale. En BFS, un vértice es seleccionado a la vez cuando es visitado y marcado luego sus adyacentes son visitados y almacenados en la cola. Es más lento que DFS.
Ex-
A / \ B C / / \ D E F
La salida es:
A, B, C, D, E, F
Depth First Search
DFS significa Depth First Search es una técnica basada en bordes. Utiliza la estructura de datos de la pila, realiza dos etapas, primero los vértices visitados son empujados en la pila y segundo si no hay vértices entonces los vértices visitados son saltados.
Ex-
A / \ B C / / \ D E F
La salida es:
A, B, D, C, E, F
BFS vs DFS
| S.NO | BFS | DFS |
|---|---|---|
| DFS significa Depth First Search. | ||
| DFS(Depth First Search) utiliza la estructura de datos Stack. | ||
| En DFS, podríamos atravesar más aristas para llegar a un vértice de destino desde un origen. | ||
| BFS considera primero a todos los vecinos y por lo tanto no es adecuado para árboles de decisión utilizados en juegos o rompecabezas. | DFS es más adecuado para problemas de juegos o rompecabezas. Tomamos una decisión, luego exploramos todos los caminos a través de esta decisión. Y si esta decisión lleva a una situación de victoria, nos detenemos. | La complejidad temporal de BFS es O(V + E) cuando se utiliza la lista de adyacencia y O(V^2) cuando se utiliza la matriz de adyacencia, donde V representa los vértices y E las aristas. | La complejidad temporal de DFS es también O(V + E) cuando se utiliza la lista de adyacencia y O(V^2) cuando se utiliza la matriz de adyacencia, donde V representa los vértices y E las aristas. |
Por favor, vea también BFS vs DFS para el árbol binario para las diferencias de un árbol binario Traversal.