Diferença entre BFS VS DFS
A Pesquisa por Largura (BFS) e a Pesquisa por Profundidade (DFS) são dois algoritmos importantes usados para pesquisa. A Pesquisa por Largura Primeiro inicia sua pesquisa a partir do primeiro nó e, em seguida, move-se pelos níveis mais próximos do nó raiz, enquanto o algoritmo de Pesquisa por Profundidade em Primeira Pesquisa inicia com o primeiro nó e, em seguida, conclui seu caminho para o nó final do respectivo caminho. Ambos os algoritmos atravessam todos os nós durante a pesquisa. Códigos diferentes são escritos para os dois algoritmos para executar o processo de deslocamento. Eles também são considerados como importantes algoritmos de pesquisa em Inteligência Artificial.
Neste tópico, vamos aprender sobre o BFS VS DFS.
Como o BFS e o DFS funcionam?
O mecanismo de trabalho de ambos os algoritmos é explicado abaixo com exemplos. Por favor, consulte-os para uma melhor compreensão da abordagem utilizada.
Exemplo de pesquisa de amplitude inicial
- Etapa 1: N1 é o nó raiz, portanto, começará a partir daqui. N1 está conectado com três nós N2, N3 e N4. Todos os três nós ainda não foram visitados. Então, partimos da N2 e a armazenamos na fila. Portanto, a fila denominada Q contém apenas N2.
Q: N2
- Etapa 2: o próximo nó conectado ao N1 é N3. Como atravessamos ou visitamos o nó, o armazenaremos na fila. Portanto, a fila atualizada é
Q: N3, N2
- Etapa 3: o próximo nó que está conectado ao nó raiz é N4. Vamos armazená-lo na fila.
Q: N4, N3, N2
- Etapa 4: Todos os nós conectados ao N1 são armazenados na fila. Agora, removemos o N2 da fila de acordo com o princípio FIFO (First in First Out) e encontramos os nós que estão conectados ao N2, ou seja, N5. O N5 não é visitado uma vez, portanto, o armazenaremos na fila.
Q: N5, N4, N3
- Etapa 5: todos os vértices são visitados, continuamos removendo os nós da fila até que estejam vazios.
Primeiro exemplo de pesquisa em profundidade
- Etapa 1: Começaremos com N1 como o nó inicial e armazená-lo em uma pilha S. N1 está conectado com três nós vizinhos N2, N3 e N4. Começando com N2 (você pode começar alfabeticamente ou numericamente), colocaremos isso na pilha.
S: N2 (Superior), N1
- Etapa 2: Agora, os nós vizinhos de N2 são N1 e N5. Como N1 já está presente na pilha, significa que ela é visitada, então pegaremos N5 e a colocaremos na pilha S.
S: N5 (parte superior), N2, N1
- Etapa 3: Agora, os nós vizinhos de N5 são N3 e N4. Começamos o N3 e o colocamos na pilha.
S: N3 (parte superior), N5, N2, N1
Agora o N3 está conectado aos N5 e N1, que já estão presentes na pilha, o que significa que eles são visitados. Portanto, removeremos o N3 da pilha conforme o princípio LIFO (Last in First Out First).
S: N5 (parte superior), N2, N1
- Etapa 4: Agora, colocaremos o último nó que não encontramos durante todo o percurso no N4 e o colocaremos na pilha.
S: N4 (parte superior), N5, N2, N1
- Etapa 5: agora não somos deixados de fora com outros nós; portanto, verificaremos na pilha se há algum nó conectado aos respectivos nós presentes que não sejam visitados. Se todos os nós conectados forem visitados, removeremos os nós presentes na pilha. Por exemplo, o N4 não possui nós de conexão que não verificamos, portanto o removeremos da pilha. Da mesma forma, podemos verificar outros nós. O algoritmo para quando a pilha estiver vazia.
Comparação cara a cara entre BFS e DFS (infográficos)
Abaixo estão as 6 principais diferenças entre o BFS VS DFS
Principais diferenças entre BFS e DFS
Vamos discutir algumas das principais diferenças importantes entre BFS e DFS
- A Pesquisa por Largura Primeiro (BFS) inicia no nó raiz e visita todos os respectivos nós conectados a ele, enquanto o DFS inicia no nó raiz e completa o caminho completo anexado ao nó.
- O BFS segue a abordagem da fila, enquanto o DFS segue a abordagem da pilha.
- A abordagem usada no BFS é ideal, enquanto o processo usado no DFS não é ideal.
- Se nosso objetivo é encontrar o caminho mais curto que o BFS, é preferível ao DFS.
Tabela de comparação BFS e DFS
Vamos discutir a melhor comparação entre BFS e DFS
| BFS | DFS |
| O formulário completo do BFS é a Pesquisa de Largura Primeiro. | O formulário completo do DFS é a profundidade da primeira pesquisa |
| O BFS deve encontrar a menor distância e começa no primeiro nó ou raiz e move-se por todos os seus nós conectados aos respectivos nós. Você pode obter uma visão clara de seu mecanismo de trabalho depois de seguir o exemplo abaixo. | O DFS segue uma abordagem baseada em profundidade e completa o caminho completo através de todos os nós conectados ao respectivo nó. Você pode obter uma visão clara de seu mecanismo de trabalho depois de seguir o exemplo abaixo. |
| Isso é feito usando o princípio Fila, que é a abordagem FIFO (First In First Out). | Isso é feito usando o princípio Stack, que é a abordagem Last In First Out (LIFO). |
| Os nós percorridos mais de uma vez são removidos da fila. | Os nós visitados são inseridos na pilha e, posteriormente, se não houver mais nós a serem visitados, eles serão removidos. |
| É comparativamente mais lento que a Profundidade da primeira pesquisa. | É mais rápido que o algoritmo de busca em largura. |
| A alocação de memória é mais do que o algoritmo Depth First Search. | A alocação de memória é comparativamente menor que o algoritmo de busca em largura |
Conclusão
Existem muitas aplicações nas quais os algoritmos acima são usados como aprendizado de máquina ou para encontrar soluções relacionadas à inteligência artificial etc. Eles são usados principalmente em gráficos para descobrir se é bipartido ou não, para detectar ciclos ou componentes conectados. Eles também são considerados como algoritmos importantes para encontrar o caminho ou para encontrar a menor distância. Dependendo dos requisitos da empresa, podemos usar dois algoritmos. No entanto, a Pesquisa por Largura-Primeira é considerada uma maneira ideal, e não o algoritmo de Pesquisa por Profundidade-Primeira.
Artigos recomendados
Este é um guia para o BFS VS DFS. Aqui discutimos as principais diferenças do BFS VS DFS com infográficos e tabela de comparação. Você também pode consultar os seguintes artigos para saber mais -
- Algoritmo BFS
- TeraData vs Oracle
- Big Data x Data Warehouse
- Big Data vs Apache Hadoop: As 4 principais comparações que você deve aprender