Usuário:Aexpedito/Página de testes1
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 realizados 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 infileirados, 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 infileirados 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 infileirar o seu vizinho na cor branca que será o vértice pai deste na representação em árvore gerada.
Características editar
Complexidade de Tempo editar
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 , 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 desinfileirado uma unica vez.
Complexidade de Espaço editar
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 onde representa o número total de vértices no grafo.
Pseudocódigo editar
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
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,5; Fila(F)=4,5. Vértices Marcados= 6,4,5,3; Fila(F)=4,5,3. Vértices Marcados= 6,4,5,3; Fila(F)=5,3. Vértices Marcados= 6,4,5,3,1; Fila(F)=5,3,1. Vértices Marcados= 6,4,5,3,1,2; Fila(F)=5,3,1,2. Vértices Marcados= 6,4,5,3,1,2; Fila(F)=3,1,2. Vértices Marcados= 6,4,5,3,1,2; Fila(F)=1,2. Vértices Marcados= 6,4,5,3,1,2; Fila(F)=2. Vértices Marcados= 6,4,5,3,1,2; Fila(F)=∅.
Observe que o algoritmo percorreu todos os vértices e arestas do grafo.
Exemplo 2 editar
Aplicando o pseudocódigo nesse grafo de cidades alemãs e iniciando o algoritmo na cidade de Frankfurt, repare que para montar a arvore 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
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;
}