Motivation
Lição 2 de 9 do curso Busca em Largura (BFS) - Algoritmos de Grafos da Coddy.
O BFS utiliza uma fila (first in, first out - primeiro a entrar, primeiro a sair) para que os vértices sejam processados na ordem exata em que são descobertos, o que produz a exploração camada por camada.
Por que aprender BFS?
- Caminhos mais curtos: em um grafo não ponderado, o BFS encontra o caminho com o menor número de arestas do início até todos os outros vértices.
- Simples e linear: ele é executado em O(V + E) com uma fila e um marcador de visitados.
- Em todo lugar: saltos mais curtos em redes, "word ladders", resolução de labirintos e travessia de árvore em ordem de nível são todos BFS.
Assim como no DFS, enfileiramos os vizinhos de um vértice em ordem crescente para que os resultados sejam previsíveis.
Experimente você mesmo
Esta lição não inclui um desafio de código.
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
