Busca em largura - BFS

Busca em largura - BFS

1. Busca em largura Marcos Castro

2. Busca em largura A busca em largura é um algoritmo de busca em grafos onde parte de um vértice e explora todos os vértices vizinhos. Então para cada um desses vértices mais próximos, explora-se os seus vizinhos não visitados e assim sucessivamente. Trata-se de uma busca não-informada que expande e examina todos os vértices de um grafo. Podemos dizer que o algoritmo realiza uma busca exaustiva no grafo. 2

3. Busca em largura O algoritmo deve garantir que nenhum vértice será visitado mais de uma vez. A BFS utiliza a estrutura fila para garantir a ordem de chegada dos vértices. As visitas aos vértices são realizadas através da ordem de chegada na fila e um vértice que já foi marcado não pode entrar novamente na fila. 3

4. Busca em largura 4 1 2 3 4 5 6 7

5. Busca em largura 5 1 2 3 4 5 6 7

6. Busca em largura 6 1 2 3 4 5 6 7

7. Busca em largura 7 1 2 3 4 5 6 7

8. Busca em largura 8 1 2 3 4 5 6 7

9. Busca em largura 9 1 2 3 4 5 6 7

10. Busca em largura 10 1 2 3 4 5 6 7

11. Busca em largura 11 1 2 3 4 5 6 7

12. Busca em largura Algoritmo: 12

13. Busca em largura Complexidade de tempo é O(|E| + |V|). Complexidade de espaço é O(|V|). |E| é a quantidade de arestas. |V| é a quantidade de vértices. 13

14. Contato [email protected] www.geeksbr.com www.twitter.com/mcastrosouza www.github.com/marcoscastro http://youtube.com/c/marcoscastrosouza 14