Busca em largura

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou se(c)ção não cita fontes fiáveis e independentes (desde agosto de 2012). Por favor, adicione referências e insira-as no texto ou no rodapé, conforme o livro de estilo. Conteúdo sem fontes poderá ser removido.
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[editar | editar código-fonte]

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 retornar 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 n+a com a≥1, 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[editar | editar código-fonte]

Complexidade de Tempo[editar | editar código-fonte]

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 desinfileirado uma unica vez.

Complexidade de Espaço[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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,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[editar | editar código-fonte]

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[editar | editar código-fonte]

int BuscaEmLargura(Grafo *G, Fila *F, int raiz){
    int *verticesMarcados = (int*)malloc(G->NumVertices * sizeof(int));//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[editar | editar código-fonte]

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[editar | editar código-fonte]

  • 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[editar | editar código-fonte]