Busca em largura

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências. Conteúdo não verificável pode ser removido.—Encontre fontes: ABW  • CAPES  • Google (N • L • A) (Agosto de 2012)

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]

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[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 ${\displaystyle O(|E|+|V|)}$, onde ${\displaystyle |E|}$ significa o tempo total gasto nas operações sobre todas as arestas do grafo onde cada operação requer um tempo constante ${\displaystyle O(1)}$ sobre uma aresta, e ${\displaystyle |V|}$ que significa o número de operações sobre todos os vértices que possui uma complexidade constante ${\displaystyle O(1)}$ para cada vértice uma vez que todo vértice é enfileirado e desenfileirado uma única 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 ${\displaystyle O(|V|)}$ onde ${\displaystyle |V|}$ representa o número total de vértices no grafo.

História[editar | editar código-fonte]

O algoritmo de busca em largura foi inventado pela primeira vez por Konrad Zuse em sua tese de doutorado sobre a linguagem de programação Plankalkül, mas como sua tese rejeitada porque Zuse esqueceu de pagar a taxa de matrícula, ela acabou esquecida e só foi publicada inteira em 1972. O algoritmo acabou sendo reinventado novamente em 1959 por Edward F. Moore, que o utilizou para encontrar o caminho mais curto para sair de um labirinto.^[1]

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]

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[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.

C[editar | editar código-fonte]

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[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. 

Exemplo de Implementação em JavaScript[editar | editar código-fonte]

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

Exemplo de Implementação em Python[editar | editar código-fonte]

Uma implementação em Python usando um array bidimensional representando um mapa. Esta versão é usada para encontrar o caminho mais curto dentro de um grid.

def solve(start_row, start_col):     q = []     q.append((start_row, start_col))     visited = [[False for i in range(cols)] for j in range(rows)]     visited[start_row][start_col] = True      prev = [[None for i in range(cols)] for j in range(rows)]     while len(q) > 0:         row, col = q.pop(0)         if m[row][col] == 'E':             return prev          # Check adjacent cells         for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:             next_row = row + dr             next_col = col + dc             if (                 next_row >= 0 and next_row < rows and                 next_col >= 0 and next_col < cols and                 not visited[next_row][next_col] and                 m[next_row][next_col] != '#'             ):                 q.append((next_row, next_col))                 visited[next_row][next_col] = True                 prev[next_row][next_col] = (row, col)      return None  def reconstructPath(start_row, start_col, end_row, end_col, prev):     path = []     row, col = end_row, end_col     while (row, col) != (start_row, start_col):         path.append((row, col))         row, col = prev[row][col]     path.append((start_row, start_col))     path.reverse()     return path  def bfs(start_row, start_col, end_row, end_col):     prev = solve(start_row, start_col)     if prev is None:         print("Caminho não encontrado.")         return []     return reconstructPath(start_row, start_col, end_row, end_col, prev)  m = [     ['S', '.', '.', '.', '.', '.', '.', '.', '.'],     ['.', '#', '#', '.', '#', '.', '#', '#', '.'],     ['.', '.', '.', '.', '#', '.', '.', '.', '.'],     ['#', '#', '.', '.', '.', '#', '#', '#', '#'],     ['.', '.', '.', '.', '.', '.', '.', '.', '.'],     ['.', '#', '#', '#', '#', '.', '.', '#', '.'],     ['.', '.', '.', '.', '#', '.', '.', '.', 'E'] ]  rows = len(m) cols = len(m[0]) start_row = 0 start_col = 0 end_row = 0 end_col = 0  for i in range(rows):     for j in range(cols):         if m[i][j] == 'S':             start_row = i             start_col = j         if m[i][j] == 'E':             end_row = i             end_col = j  print("Labirinto:") for row in m:     print(' '.join(row))  print("\nBuscando um caminho:")  path = bfs(start_row, start_col, end_row, end_col)  if len(path) > 0:     print("Caminho encontrado:")     for row, col in path:         m[row][col] = 'P'     for row in m:         print(' '.join(row)) else:     print("Caminho não encontrado.") 

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]

• Busca em profundidade
• Teoria dos Grafos

Referências

• Portal das tecnologias de informação