Busca em largura

Ordem dos vértices explorados na busca em largura

Na teoria dos grafos, busca em largura (ou busca em amplitude, também conhecido em inglês por Breadth-First Search - BFS) é um algoritmo de busca em grafos utilizado para realizar uma busca ou travessia num grafo e estrutura de dados do tipo árvore. Intuitivamente, você começa pelo vértice raiz e explora todos os vértices vizinhos. Então, para cada um desses vértices mais próximos, exploramos os seus vértices vizinhos inexplorados e assim por diante, até que ele encontre o alvo da busca.

Definição

Percurso realizado pelo algoritmo

Formalmente, uma busca em largura é um método de busca não-informada (ou desinformada) que expande e examina sistematicamente todos os vértices de um grafo direcionado ou não-direcionado. Em outras palavras, podemos dizer que o algoritmo realiza uma busca exaustiva num grafo passando por todas as arestas e vértices do grafo. Sendo assim, o algoritmo deve garantir que nenhum vértice ou aresta será visitado mais de uma vez e, para isso, utiliza uma estrutura de dados fila para garantir a ordem de chegada dos vértices. Dessa maneira, as visitas aos vértices são realizadas através da ordem de chegada na estrutura fila e um vértice que já foi marcado não pode entrar novamente a esta estrutura.

Uma analogia muito conhecida (figura ao lado) para demonstrar o funcionamento do algoritmo é pintando os vértices de branco, cinza e preto. Os vértices na cor branca ainda não foram marcados e nem enfileirados, os da cor cinza são os vértices que estão na estrutura fila e os pretos são aqueles que já tiveram todos os seus vértices vizinhos enfileirados e marcados pelo algoritmo.

Tal mecanismo permite que se descubra todos os vértices a uma distância n do vértice raiz antes de qualquer outro vértice de distancia maior que n, sendo n o número de arestas para atingir qualquer outro vértice no grafo considerado. Essa característica do algoritmo permite construir uma árvore de distâncias mínimas (menor número de arestas) entre o vértice raiz e os demais, sendo que o vértice responsável por enfileirar o seu vizinho na cor branca que será o vértice pai deste na representação em árvore gerada.

Características

Complexidade de Tempo

Considerando um grafo representado em listas de adjacência, o pior caso, aquele em que todos os vértices e arestas são explorados pelo algoritmo, a complexidade de tempo pode ser representada pela seguinte expressão $O(|E|+|V|)$, onde $|E|$ significa o tempo total gasto nas operações sobre todas as arestas do grafo onde cada operação requer um tempo constante $O(1)$ sobre uma aresta, e $|V|$ que significa o número de operações sobre todos os vértices que possui uma complexidade constante $O(1)$ para cada vértice uma vez que todo vértice é enfileirado e desenfileirado uma unica vez.

Complexidade de Espaço

Quando o número de vértices no grafo é conhecido e supondo-se a representação deste em listas de adjacência, a complexidade de espaço do algoritmo pode ser representada por $O(|V|)$ onde $|V|$ representa o número total de vértices no grafo.

Pseudocódigo

A seguir é apresentado um pseudocódigo do algoritmo busca em largura para uma estrutura de dados grafo com lista de adjacência. A letra F representa uma fila (FIFO) inicialmente vazia, G é o grafo em questão e s, v, w representam vértices do grafo onde listaDeAdjacência representa a lista de adjacência de um vértice.

BuscaEmLargura
   escolha uma raiz s de G
   marque s
   insira s em F
   enquanto F não está vazia faça
      seja v o primeiro vértice de F
      para cada w ∈ listaDeAdjacência de v faça
         se w não está marcado então
            visite aresta entre v e w
            marque w
            insira w em F
         senao se w ∈ F entao
            visite aresta entre v e w
         fim se
      fim para
      retira v de F
   fim enquanto

Exemplo 1

Grafo exemplo 1

Seguindo os passos do pseudocódigo acima e iniciando no vértice 6 da figura ao lado, o algoritmo estará com a sequência de vértices marcados e a fila assim:

Vértices Marcados= ∅; Fila(F)=∅.
Vértices Marcados= 6; Fila(F)=6.
Vértices Marcados= 6,4; Fila(F)=6,4.
Vértices Marcados= 6,4; Fila(F)=4.
Vértices Marcados= 6,4,3; Fila(F)=4,3.
Vértices Marcados= 6,4,3,5; Fila(F)=4,3,5.
Vértices Marcados= 6,4,3,5; Fila(F)=3,5.
Vértices Marcados= 6,4,3,5,2; Fila(F)=3,5,2.
Vértices Marcados= 6,4,3,5,2; Fila(F)=5,2.
Vértices Marcados= 6,4,3,5,2,1; Fila(F)=5,2,1.
Vértices Marcados= 6,4,3,5,2,1; Fila(F)=2,1.
Vértices Marcados= 6,4,3,5,2,1; Fila(F)=1.
Vértices Marcados= 6,4,3,5,2,1; Fila(F)=∅.

Exemplo 2

Aplicando o pseudocódigo nesse grafo de cidades alemãs e iniciando o algoritmo na cidade de Frankfurt, repare que para montar a árvore da figura foi necessário gravar na figura apenas as arestas que são processadas na primeira condição "se" do pseudocódigo (se w não está marcado então). Caso as arestas desse exemplo não fossem valoradas (como no primeiro exemplo) ficaria fácil encontrar a distância para o vértice raiz com o algoritmo busca em largura, mas, para o grafo deste exemplo (que são valoradas) pesquise por Algoritmo de Dijkstra para encontrar o menor caminho de um vértice a outro.

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

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

C

int BuscaEmLargura(Grafo *G, Fila *F, int raiz){
    int verticesMarcados[NumVertices];//vetor de vertices marcados
    int tamVerticesMarcados= 0;
    int vertice1;
    no_lista *p;
 
    verticesMarcados[0] = raiz;//marca raiz
    tamVerticesMarcados++;    

    PoeVerticeNaFila(F , raiz); //poe raiz na fila

    while(!FilaVazia(F)){//enquanto a fila nao esta vazia
        vertice1 = F->ini->vertice;//vertice que esta no inicio da fila     
         p = G->Ladj[vertice1-1].inicio;// Ladj = lista de adjacencia de vertice1

        while(p!=NULL){//enquanto a lista de adjacencia do vertice1 nao acaba
            if(!BuscaVertice(p->vertice, verticesMarcados, tamVerticesMarcados)){//busca p->vertice no vetor verticesMarcados
                verticesMarcados[tamVerticesMarcados++] = p->vertice;//marcou p->vertice
                PoeVerticeNaFila(F , p->vertice);//poe p->vertice na fila 
                //arestas que compoem arvore geradora mínima, aresta (vertice1, p->vertice)
            }
            else
            if(WPertenceF(p->vertice, F)){//se p->vertice pertence a F
                //arestas (vertice1, p->vertice) que não compoem árvore geradora mínima
            }          
            p = p->prox;
        }
        RetiraVerticeFila(F);
    }
    return 0;
}

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.

Exemplo de Implementação em JavaScript

function BFS(nodos, inicio, fim){
    console.log(inicio);
    console.log(fim);
    var fila = new Array();

    nodos[inicio].visita = 2;
    fila.push(nodos[inicio]);

    if (inicio != fim) {
        while (fila.length > 0) {
            nodo = fila[0];
            fila.shift();
            for (var i = 0; i < nodo.filhosObj.length; i++) {
                vertice = nodo.filhosObj[i].idVertice2;
                if (nodos[vertice].visita != 2) {
                    nodos[vertice].visita = 2;
                    if (nodos[vertice].relIdObj == fim) {
                        console.log(nodos[vertice]);
                        return false;
                    };
                    fila.push(nodos[vertice]);
                    console.log(nodos[vertice]);
                }else if(fila.indexOf(nodos[vertice])){
                    nodos[vertice].visita = 2;
                    if (nodos[vertice].relIdObj == fim) {
                        console.log(nodos[vertice]);
                        return false;
                    };
                    console.log(nodos[vertice]);
                };
            };
        };
    }else{
        console.log(nodos[inicio]);
    };
};

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