BFS e DFS são os métodos de deslocamento usados na pesquisa de um gráfico. O percurso do gráfico é o processo de visitar todos os nós do gráfico. Um grafo é um grupo de vértices 'V' e arestas 'E' conectando-se aos vértices.
Gráfico de comparação
| Base para comparação | BFS | DFS |
|---|---|---|
| Basic | Algoritmo baseado em vértices | Algoritmo Edge-based |
| Estrutura de dados usada para armazenar os nós | Fila | Pilha |
| Consumo de memória | Ineficiente | Eficiente |
| Estrutura da árvore construída | Largo e curto | Estreito e longo |
| Travessia de moda | Vértices não visitados mais antigos são explorados em primeiro lugar. | Vértices ao longo da borda são explorados no começo. |
| Otimalidade | Ótima para encontrar a distância mais curta, não no custo. | Não ideal |
| Aplicação | Examina gráfico bipartido, componente conectado e caminho mais curto presente em um gráfico. | Examina gráfico conectado de duas arestas, gráfico fortemente conectado, gráfico acíclico e ordem topológica. |
Definição de BFS
Breadth First Search (BFS) é o método de deslocamento usado nos gráficos. Ele usa uma fila para armazenar os vértices visitados. Neste método a ênfase está nos vértices do gráfico, um vértice é selecionado no início, então é visitado e marcado. Os vértices adjacentes ao vértice visitado são então visitados e armazenados na fila sequencialmente. Da mesma forma, 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 gráfico, em outras palavras, ele percorre os nós inexplorados mais rasos primeiro.
Exemplo
Nós temos um gráfico cujos vértices são A, B, C, D, E, F, G. Considerando A como ponto de partida. As etapas envolvidas no processo são:
- 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 o Vertex A é removido.
- Agora, B na extremidade da frente da fila é removido junto com o armazenamento de seus sucessores, vértices E e F.
- O vértice D está na extremidade dianteira da fila é removido e seu nó conectado F já é visitado.
- O vértice G é removido da fila e tem o sucessor E que já é visitado.
- Agora, E e F são removidos da fila e seu sucessor, o vértice C, é percorrido e armazenado na fila.
- Por fim, C também é removido e a fila está vazia, o que significa que estamos prontos.
- A saída gerada é - A, B, D, G, E, F, C.
O BFS pode ser útil para descobrir se o gráfico conectou componentes ou não. E também pode ser usado na detecção de um gráfico bipartido .
Um gráfico é bipartido quando os vértices do gráfico são divididos em dois conjuntos disjuntos; Nenhum dois vértices adjacentes residiria no mesmo conjunto. Outro método de verificação de um gráfico bipartido é verificar a ocorrência de um ciclo ímpar no gráfico. Um gráfico bipartido não deve conter um ciclo ímpar.
O BFS também é melhor em encontrar o caminho mais curto no gráfico que pode ser visto como uma rede.
Definição de DFS
O método de deslocamento DFS (Depth First Search) usa a pilha para armazenar os vértices visitados. O DFS é o método baseado em arestas e funciona de maneira recursiva, em que 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 mais inexplorados mais profundos são percorridos antes de tudo. DFS atravessar / visitar cada vértice exatamente uma vez e cada borda é inspecionada exatamente duas vezes.
Exemplo
Semelhante ao BFS permite obter o mesmo gráfico para executar operações do DFS e as etapas envolvidas são:
- Considerando A como o vértice inicial que é explorado e armazenado na pilha.
- O vértice B sucessor de A é armazenado na pilha.
- O 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, isto é, G, é armazenado na pilha.
- O vértice G tem dois vértices conectados, e ambos já são visitados, então G é retirado da pilha.
- Da mesma forma, E também foi removido.
- Agora, o vértice B está no topo da pilha, seu outro nó (vértice) F é explorado e armazenado na pilha.
- O vértice F tem dois sucessores C e D, entre eles, C é primeiro percorrido e armazenado na pilha.
- Vertex C tem apenas um predecessor que já é 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 possui nenhum nó não visitado, portanto, D é removido.
- Da mesma forma, F, B e A também são exibidos.
- A saída gerada é - A, B, E, G, F, C, D.
As aplicações do DFS incluem a inspeção de dois grafos conectados à borda, gráfico fortemente conectado, gráfico acíclico e ordem topológica .
Um gráfico é chamado de duas arestas conectadas se, e somente se, ele permanecer conectado mesmo se uma de suas arestas for 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 conectado.
O gráfico fortemente conectado é um grafo no qual deve existir um caminho entre pares ordenados de vértices. O DFS é usado no gráfico direcionado para pesquisar o caminho entre cada par ordenado de vértices. O DFS pode facilmente resolver problemas de conectividade.
Principais diferenças entre o BFS e o DFS
- O BFS é um algoritmo baseado em vértices, enquanto o DFS é um algoritmo baseado em borda.
- A estrutura de dados da fila é usada no BFS. Por outro lado, o DFS usa pilha ou recursão.
- O espaço de memória é utilizado eficientemente no DFS, enquanto a utilização de espaço no BFS não é efetiva.
- O BFS é o algoritmo ideal, enquanto o DFS não é ideal.
- O DFS constrói árvores estreitas e longas. Em contrapartida, a BFS constrói uma árvore larga e curta.
Conclusão
BFS e DFS, ambas as técnicas de busca de gráficos têm tempo de execução semelhante, mas consumo de espaço diferente, o DFS ocupa espaço linear porque temos que lembrar um único caminho com nós inexplorados, enquanto o BFS mantém todos os nós na memória.
O DFS produz soluções mais profundas e não é o ideal, mas funciona bem quando a solução é densa, enquanto o BFS é o ideal, que busca primeiro o objetivo ideal.
