Algoritmos de busca

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (480 palavras )
  • Download(s) : 0
  • Publicado : 31 de maio de 2012
Ler documento completo
Amostra do texto
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

Algoritmode 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, oalgoritmo 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 deum 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 outraspropriedades 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 principalcaracterí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 emLargura
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á maistempo.
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” iguala 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ósadjacentes 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...
tracking img