o principal diferença entre BFS e DFS é que O BFS ou Breadth First Search prossegue nível após nível, enquanto o DFS ou Depth First Search segue um caminho do nó inicial ao final e então se move para o outro caminho do início ao fim e assim por diante, até visitar todos os nós.

Um gráfico é uma estrutura de dados não linear que organiza os elementos de dados como um modelo de rede. Os nós em um grafo são chamados de vértices e as arestas conectam esses nós. É possível resolver a maioria dos problemas de gráfico usando métodos de pesquisa. Pesquisa de amplitude primeiro (BFS) e pesquisa de profundidade primeiro (DFS) são métodos de pesquisa comuns em uso. Em resumo, o BFS usa uma fila enquanto o DFS usa uma pilha.

BFS, DFS

O que é BFS

BFS significa Breath First Search. Ele usa uma fila. O processo é como se segue.

Um exemplo é o seguinte.

Figura 1: BFS

Suponha que o vértice inicial na imagem acima seja 1. Os nós conectados a 1 são 2 e 4. Portanto, podemos colocar 1, 2 e 4 em uma fila. A saída é 1, 2, 4. Para 1, não há vértices restantes. Portanto, podemos remover 1 da fila. Agora podemos passar para 2. Os vértices adjacentes de 2 são 3, 5 e 6. Portanto, podemos colocar 3, 5 e 6 na fila. A saída é 1, 2, 4, 3, 6. Além desses três números, não há vértices adjacentes conectados a 2. Portanto, podemos remover 2 da fila. Agora, vamos passar para 4. O único nó adjacente a 4 é 6. Ele já foi visitado. Não há mais vértices para 4. Portanto, podemos remover 4 da fila. Você tem que repetir este processo até que a fila esteja vazia. Indica o término da operação de busca.

O que é DFS

DFS significa Profundidade primeira pesquisa. O processo é como se segue.

Visite o vértice não visitado adjacente e marque-o como visitado. Em seguida, exiba-o na saída e coloque-o na pilha.

Se nenhum vértice adjacente for encontrado, abra o vértice da pilha.

Continue com as duas etapas acima até que a pilha esteja vazia.

Figura 2: DFS

O vértice inicial é A. Ele é colocado na pilha. Os vértices adjacentes são B e E. Considere B. Podemos empurrar B para a pilha. Como não há nós adjacentes a B, podemos retirar B da pilha. A saída é A B. O nó adjacente restante a A é E, portanto, podemos colocar E na pilha. Agora a saída é A B E.

Como não há nós adjacentes a A, podemos retirar ‘A’ da pilha. Os nós adjacentes para E são C e H. Agora, considere C. Podemos empurrar C para a pilha. A saída é A B E C. O processo continua até que a pilha esteja vazia. Ele termina a operação de pesquisa.

Diferença entre BFS e DFS

Definição

BFS (Breadth first search) é um algoritmo de passagem de gráfico que começa a atravessar o gráfico a partir do nó raiz e explora todos os nós vizinhos. DFS (Depth first search) é um algoritmo que começa com o nó inicial do gráfico e vai cada vez mais fundo até encontrar o nó necessário ou o nó que não tem filhos. Portanto, esta é a principal diferença entre BFS e DFS.

Forma longa

Enquanto BFS significa Pesquisa em Largura, DFS significa Pesquisa Primeira em Profundidade.

Método de armazenamento de nós

Outra diferença importante entre o BFS e o DFS é que o BFS usa a fila enquanto o DFS usa a pilha.

Consumo de Memória

Método de Traversing

O método de conversão é outra diferença entre BFS e DFS. O BFS se concentra em visitar os vértices não visitados mais antigos primeiro, enquanto o DFS se concentra em visitar os vértices ao longo da aresta no início.

Conclusão

BFS e DFS são dois métodos de pesquisa para localizar um elemento em um gráfico. A principal diferença entre o BFS e o DFS é que o BFS prossegue nível após nível, enquanto o DFS segue um caminho do nó inicial ao final e então se move para o outro caminho do início ao fim e assim por diante até visitar todos os nós.

Referência:

1. Algoritmo de primeira pesquisa de amplitude | Pseudo Código | Introdução, Education 4u, 22 de março de 2018, disponível aqui.2. Largura primeira pesquisa | Exemplos BFS |, Education 4u, 22 de março de 2018, disponível aqui.3. Algoritmo de primeira pesquisa de profundidade | Graph Traversal Algorithm |, Education 4u, 22 de março de 2018, disponível aqui.4. “Algoritmo BFS - Javatpoint.” Www.javatpoint.com, disponível aqui.5. “Algoritmo DFS - Javatpoint.” Www.javatpoint.com, disponível aqui.