Breadth First Search
BFS significa Breadth First Search é uma técnica baseada em vértices para encontrar um caminho mais curto no gráfico. Ela usa uma estrutura de dados em fila que segue primeiro em primeiro out. Na BFS, um vértice é selecionado de cada vez que é visitado e marcado, em seguida, seus adjacentes são visitados e armazenados na fila. É mais lento que DFS.
Ex-
A / \ B C / / \ D E F
Output is:
A, B, C, D, E, F
Depth First Search
DFS significa Depth First Search é uma técnica baseada em bordas. Ela usa a estrutura de dados Stack, realiza duas etapas, primeiro os vértices visitados são empilhados e segundo se não houver vértices, então os vértices visitados são popped.
Ex-
A / \ B C / / \ D E F
Output is:
A, B, D, C, E, F
BFS vs DFS
| S.NÃO | BFS | DFS |
|---|---|---|
| BFS significa Breadth First Search. | DFS significa Depth First Search. | |
| BFS(Breadth First Search) usa a estrutura de dados Queue para encontrar o caminho mais curto. | DFS(Depth First Search) usa estrutura de dados Stack. | |
| Na DFS, podemos atravessar mais bordas para chegar a um vértice de destino a partir de uma fonte. | ||
| BFS é mais adequado para procurar vértices que estão mais próximos da fonte dada. | DFS é mais adequado quando há soluções longe da fonte. | |
| BFS considera todos os vizinhos primeiro e, portanto, não é adequado para a tomada de decisão árvores usadas em jogos ou puzzles. | DFS é mais adequado para jogos ou quebra-cabeças. Nós tomamos uma decisão, então exploramos todos os caminhos através desta decisão. E se esta decisão leva a uma situação de vitória, nós paramos. | A complexidade temporal do BFS é O(V + E) quando a Adjacency List é usada e O(V^2) quando a Adjacency Matrix é usada, onde V significa vértices e E significa bordas. | A Complexidade temporal da DFS também é O(V + E) quando Lista de Adjacência é usada e O(V^2) quando Matriz de Adjacência é usada, onde V significa vértices e E significa bordas. |
Veja também BFS vs DFS para Árvore Binária para as diferenças para uma Traversal de Árvore Binária.