Busca em largura
Origem: Wikipédia, a enciclopédia livre.
Na ciência da computação, busca em largura (busca em largura-primeiro ou busca em amplitude) é um algoritmo de procura de árvore usado para realizar uma busca ou travessia numa árvore, estrutura de árvore ou grafo. Intuitivamente, você começa pelo nó raiz e explora todos os nós vizinhos. Então, para cada um desses nós mais próximos, exploramos os seus nós vizinhos inexplorados e assim por diante, até que ele encontre o alvo da busca.
Índice |
[editar] Definição Formal
Formalmente, uma busca em largura é um método de busca não-informada (ou desinformada) que expande e examina sistematicamente todos os nós de uma árvore, em busca de uma solução. Em outras palavras, podemos dizer que seu algoritmo realiza uma busca exaustiva numa árvore inteira, sem considerar o seu alvo de busca, até que ele o encontre. Ele não utiliza uma heurística.
Do ponto de vista do algoritmo, todos os nós filhos obtidos pela expansão de um nó são adicionados a uma fila (FIFO). Em implementações típicas, nós que ainda não foram examinados por seus vizinhos são colocados num container (como por exemplo uma fila ou lista ligada) que é chamado de “aberto”. Uma vez examinados, são colocados num container “fechado”.
Quando realizamos a busca do menor caminho num grafo cíclico ponderado (ou seja, que não é uma árvore), um algoritmo de busca em largura pode ser adaptado, mantendo-se um bit em cada nó para indicar qual deles já foi visitado.
- A busca em largura é completa apenas se a árvore pesquisada tem um número finito de ramos – o algoritmo irá encontrar o alvo da busca caso ele exista(ou seja, ele alcança todos os nós de uma árvore).
- A busca em largura é ótima se o custo dos passos forem idênticos – o algoritmo encontrará a solução mais “rasa” de uma árvore de busca, não necessariamente a melhor. No caso em que os passos possuem custos diferentes, a solução mais “rasa” não é necessariamente a melhor.
- A busca em largura tem complexidade linear espacial do tamanho (arestas somadas a vértices) da árvore / grafo pesquisada(o), já que ela precisa armazenar todos os nós expandidos na memória.
[editar] Exemplo
Para o grafo seguinte, uma busca em largura começando em A, assumindo-se que as arestas esquerdas do grafo apresentado sejam escolhidas antes das arestas direitas, resultará numa busca cujos nós visitados estariam na seguinte ordem : A, B, C, E, D, F, G.
[editar] Pseudocódigo
function busca_Largura (Inicio , Alvo) {
entra_fila(Fila,Inicio)
while naoVazia(Fila) {
Nodo := sai_fila(Fila)
if Nodo = Alvo {
return Nodo
}
for each Filho in Expande(Nodo) {
if naoVisitado(Filho) {
foi_visitado(Filho)
entra_fila(Fila, Filho)
}
}
}
}
[editar] Usos e extensões
A busca em largura pode ser usada para identificar componentes conectados bem como para testar bipartição em grafos. O conjunto de nós alcançados pela busca em largura são os maiores componentes conectados que contém o nó inicial. Se não houverem arestas nos nós adjacentes numa mesma camada de busca, então o grafo deve conter um número ímpar de ciclos e não ser bipartido.
