Busca em Largura - BFS
A busca em largura (breadth-first search) utiliza um grafo G e começa por um vértice qualquer. O algoritmo visita o vértice, depois visita todos os vizinhos dele, depois todos os vértices que estão à distância 2 vértice inicial, e assim por diante. O algoritmo numera os vértices, em sequência, na ordem em que eles são descobertos.
Busca em Profundidade - DFS
O algoritmo de busca em profundidade (depth-first search) começa num nó raiz e explora seus ramos o máximo possível antes de retroceder (backtracking).
Objetivo
Implementar os algoritmos BFS e DFS para extrair as árvores BFS-tree e DFS-tree dos grafos a seguir.
Metodologia
Para a implementação foi utilizada a linguagem Python, a biblioteca NetworkX e Matplotlib para desenhar o grafo.
 |
| Busca em Largura - BFS |
 |
| Busca em Profundidade - DFS |
Rodando os códigos BFS e DFS, foi possível gerar as BFS-tree e DFS-tree que podem ser visualizadas abaixo.
 |
| BFS-tree do grafo karate.paj |
 |
| BFS-tree do grafo dolphins.paj |
 |
| DFS-tree do grafo karate.paj |
 |
| DFS-tree do grafo dolphins.paj |
Nenhum comentário:
Postar um comentário