Algoritmos de busca

Trabalho realizado por:
Susana Luís nº 2110124
Ruben Santos nº 2110130
Tiago Coito nº 2111227

Disciplina: Matemática Discreta
Curso: Engenharia Informática

Algoritmos de Busca

Algoritmo de Busca
Um algoritmo que examina, sistematicamente, todos os vértices e todas as arestas de um grafo. Cada aresta é estudada uma só vez. Depois de visitar o vértice inicial de uma aresta, o algoritmo percorre aresta até visitar o seu vértice final. Para justificar a palavra "busca", devemos imaginar que o algoritmo percorre o grafo verificando todos os vértices que são acessíveis a partir de um determinado vértice em questão.
Estas buscas são caracterizadas pela ordem em que os vértices são visitados. Assim, a ordem de visita torna-se essencial se desejamos determinar outras propriedades além da mera característica de um determinado vértice ser alcançado a partir de outro. O algoritmo de busca em grafos pode então mostrar-nos outras características de grafos.
A principal característica desse algoritmo é que a busca encontra primeiro todos os vértices que estão à distância 1 da origem da busca, em seguida os que estão à distância 2, e assim por diante.

Algoritmos de Busca em Largura
No algoritmo de busca em largura, a lista de vértices obedece a política FIFO (primeiro a entrar será o primeiro a sair – Fila): o vértice que sai da lista é sempre o que está lá há mais tempo.
Neste exemplo vamos percorrer caminho entre 1 e 5. No início todos os vértices são pintados de branco.
Exemplo:
Escolhemos por exemplo o vértice de número 1, sendo marcado com “largura” igual a zero. O algoritmo pinta de cinza este vértice e o coloca em uma fila Q.

A seguir, o algoritmo retira o vértice 1 da fila Q e pinta-o de preto.
O algoritmo inclui no fim da fila todos os nós adjacentes ao vértice 1 marcando-os com “largura” igual a 1. Neste caso temos apenas o vértice 2. O vértice 2 é então pintado de cinza.
O vértice 2 é retirado da fila Q e pintado de preto, enquanto