Busca em largura

Ordem dos vértices explorados na busca em largura

Na teoria dos grafos, busca em largura (busca em largura-primeiro ou busca em amplitude, também usada a sigla em inglês BFS) é 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.

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.

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…

Exemplo 2

Exemplo de um mapa da Alemanha com algumas conexões entre as cidades.

Árvore gerada em um algoritmo BFS começando em Frankfurt.

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)
            }
        }
    }
}

Exemplo de Implementação em Object Pascal

program Busca_em_largura;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
var
  vListaNos : array[1..8] of char;
 
  function NoEsquerdo(pNoAtual: Integer): integer;
  begin
    result := (2 * pNoAtual);
  end;
  function NoDireito(pNoAtual: Integer): integer;
  begin
    result := (2 * pNoAtual) + 1;
  end;
  function busca_Largura (Inicio : integer; Alvo: Char): integer;
  var
    vAchou : Boolean;
    vLoop : integer;
  begin
    vAchou := false;
    vLoop := Inicio;
    Result := -1;
    if vListaNos[Inicio] = Alvo then begin
      vAchou := true;
      Result := Inicio;
    end;
    while (not vAchou) and (vLoop <= 8) do begin
      if vListaNos[NoEsquerdo(vLoop)] = Alvo then begin
        vAchou := true;
        Result := NoEsquerdo(vLoop);
      end else if vListaNos[NoDireito(vLoop)] = Alvo then begin
        vAchou := true;
        Result := NoDireito(vLoop);
      end;
      inc(vLoop);
    end;
  end;
 
begin
  { Busca em largura na árvore binária }
  // Preenchimento da arvore, demostração gráfica e posicionamento na mesma…
  vListaNos[1] := 'R';      {         R                 1           }
  vListaNos[2] := 'G';      {        / \               / \          }
  vListaNos[3] := 'Q';      {       G   Q             2   3         }
  vListaNos[4] := 'Y';      {      /\   /\           /\   /\        }
  vListaNos[5] := 'J';      {     Y J  B  E         4 5  6  7       }
  vListaNos[6] := 'B';      {    /                 /                }
  vListaNos[7] := 'E';      {   P                 8                 }
  vListaNos[8] := 'P';
  // Pesquisa por elementos na árvore…
  Writeln('A letra "J" esta no no numero: '+ IntToStr(busca_Largura(2, 'J')));
  Writeln('A letra "B" esta no no numero: '+ IntToStr(busca_Largura(1, 'B')));
  Writeln('A letra "R" esta no no numero: '+ IntToStr(busca_Largura(1, 'R')));
  Writeln('A letra "P" esta no no numero: '+ IntToStr(busca_Largura(4, 'P')));
  Writeln('A letra "Y" esta no no numero: '+ IntToStr(busca_Largura(1, 'Y')));
  Writeln('A letra "E" esta no no numero: '+ IntToStr(busca_Largura(1, 'E')));
  Writeln('A letra "Q" esta no no numero: '+ IntToStr(busca_Largura(1, 'Q')));
  Readln;
end.

Usos e extensões

• Achar componentes conectados
• Achar todos os nódulos contectado a apenas um componente
• Achar o menor caminho entre um nó raiz e os outros nós do grafo
• 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 houver 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.

Ver também

• Busca em profundidade
• Teoria dos Grafos