A principal diferença entre os BFS e DFS é que BFS proventos de nível por nível, enquanto DFS segue primeiro um caminho formulário inicial para o fim de nó (vértice) e, em seguida, um outro caminho, desde o início até o final, e assim por diante até que todos os nós são visitados. Além disso, BFS usa a fila para armazenar os nós, enquanto DFS usa a pilha para atravessar os nós.

BFS e DFS são os métodos de travessia utilizados na pesquisa de um grafo. Grafo transversal é o processo de visitar todos os nós do grafo. Um grafo é um grupo de vértices ‘V’ e arestas ‘E’ conectando-se aos vértices.conteúdo: BFS Vs DFS

1. Comparison Chart
2. Definition
3. Key Differences
4. Conclusion

Comparison Chart

Basis for comparison	BFS	DFS
Basic	Vertex-based algorithm	Edge-based algorithm
Data structure used to store the nodes	Queue	Stack
Memory consumption	Inefficient	Efficient
Structure da árvore construída	Wide and short	Narrow and long
Traversing fashion	os vértices não visitados mais antigos são explorados no início.	vértices ao longo da aresta são explorados no início.
optimal	Optimal for finding the shortest distance, not in cost.	Not optimal
Application	examina o grafo bipartido, componente ligado e o caminho mais curto presente num grafo.	examina o grafo conectado de duas arestas, o grafo fortemente conectado, o grafo acíclico e a ordem topológica.

Definição de BFS

Largura Primeira Search (BFS) é a travessia método utilizado em gráficos. Ele usa uma fila para armazenar os vértices visitados. Neste método a ênfase está nos vértices do grafo, um vértice é selecionado no início, então ele é visitado e marcado. Os vértices adjacentes ao vértice visitado são então visitados e armazenados na fila sequencialmente.

similarmente, os vértices armazenados são então tratados um por um, e seus vértices adjacentes são visitados. Um nó é totalmente explorado antes de visitar qualquer outro nó no grafo, em outras palavras, ele atravessa os nós inexplorados primeiro.

exemplo

temos um grafo cujos vértices são A, B, C, D, E, F, G. considerando A como ponto de partida. Os passos envolvidos no processo são:

• vértice A é expandido e armazenado na fila.
• vértices B, D E G sucessores de A, são expandidos e armazenados na fila enquanto isso vértice A removido.
• Agora B no final da fila é removido juntamente com o armazenamento de seus vértices E E F.
• o vértice D está na extremidade dianteira da fila é removido, e seu nó conectado F já está visitado.
• o vértice G é removido da fila, e tem o sucessor E que já está visitado.
• Now E F are removed from the queue, and its successor vertex C is traversed and stored in the queue.
• At last C is also removed and the queue is empty which means we are done.
• A saída gerada é-A, B, D, G, E, F, C.

Applications

BFS can be useful in finding whether the graph has connected components or not. E também pode ser usado na detecção de um grafo bipartido.

um grafo é bipartido quando os vértices do grafo são divididos em dois conjuntos disjuntos; nenhum dois vértices adjacentes residiria no mesmo conjunto. Outro método de verificar um grafo bipartido é verificar a ocorrência de um ciclo ímpar no grafo. Um grafo bipartido não deve conter ciclos ímpares.

BFS também é melhor em encontrar o caminho mais curto no grafo pode ser visto como uma rede.

definição de DFS

profundidade primeira pesquisa (DFS) método de navegação usa a pilha para armazenar os vértices visitados. DFS é o método baseado em arestas e funciona de forma recursiva onde os vértices são explorados ao longo de um caminho (aresta). A exploração de um nó é suspensa assim que outro nó inexplorado é encontrado e os nós inexplorados mais profundos são atravessados em primeiro lugar. DFS traverse / visite cada vértice exatamente uma vez e cada aresta é inspecionada exatamente duas vezes.

exemplo

semelhante a BFS permite fazer o mesmo gráfico para realizar operações DFS, e os passos envolvidos são:

• considerando A como o vértice inicial que é explorado e armazenado na pilha.
• b o vértice sucessor de A é armazenado na pilha.
• vértice B tem dois sucessores E E F, entre eles alfabeticamente E é explorado primeiro e armazenado na pilha.
• o sucessor do vértice E, ou seja, G é armazenado na pilha.
• vértice G tem dois vértices conectados, e ambos já estão visitados, então G é retirado da pilha.da mesma forma, também foram removidos.
• Agora, o vértice B está no topo da pilha, seu outro nó(vértice) F é explorado e armazenado na pilha.
• vértice F tem dois sucessores C E D, entre eles C é atravessado primeiro e armazenado na pilha.
• vértice C apenas tem um predecessor que já está visitado, por isso é removido da pilha.
• Agora o vértice D conectado a F é visitado e armazenado na pilha.
• Como o vértice D não tem quaisquer Nós não visitados, portanto D é removido.
• similarmente, F, B e A também são estourados.
• a saída gerada é-A, B, E, G, F, C, D.

Application

the applications of DFS includes the inspection of two edge connected graph, strongly connected graph, acyclic graph, and topological order.

um grafo é chamado de duas arestas conectadas se e somente se ele permanece conectado mesmo se uma de suas arestas é removida. Esta aplicação é muito útil, em redes de computadores onde a falha de um link na rede não afetará a rede restante, e ainda estaria conectada.

grafo fortemente conectado é um grafo no qual deve existir um caminho entre pares ordenados de vértices. DFS é usado no grafo dirigido para pesquisar o caminho entre cada par ordenado de vértices. DFS pode facilmente resolver problemas de conectividade.

Conclusão

BFS e o DFS, ambos do gráfico técnicas de pesquisa semelhantes tempo de execução diferentes, mas o consumo de espaço, de DFS toma espaço linear, porque temos que lembrar único caminho inexplorado nós, enquanto BFS cada nó mantém na memória.

DFS produz soluções mais profundas e não é ideal, mas funciona bem quando a solução é densa, enquanto BFS é ótima, que busca o objetivo ideal no início.