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
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
editarComplexidade de Tempo
editarConsiderando 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 , onde significa o tempo total gasto nas operações sobre todas as arestas do grafo onde cada operação requer um tempo constante sobre uma aresta, e que significa o número de operações sobre todos os vértices que possui uma complexidade constante para cada vértice uma vez que todo vértice é enfileirado e desenfileirado uma única vez.
Complexidade de Espaço
editarQuando 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 onde representa o número total de vértices no grafo.
História
editarO 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
editarA 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
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
editarAplicando 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.
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
editarprogram 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
editarfunction 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
editarUma 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- 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
editarReferências
- ↑ Schrijver, Alexander (2012). «On the History of the Shortest Path Problem» (PDF). Deutsche Mathematiker-Vereinigung e.V., Berlin. Documenta Mathematica. Extra Volume ISMP (2012) (Extra Volume ISMP (2012)): 8. Consultado em 20 de julho de 2023
