Busca em Nível [Complex Systems]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.

====== Busca em Nível ======

Na busca em nível, a partir de um nó arbitrário //a//, primeiro procuramos seus nós adjacentes. Em seguida, os nós adjacentes a esses e assim por diante. Pictoricamente, a busca se dá quase como círculos concêntricos de ondas em um lago. A figura abaixo mostra os primeiros nós visitados em um grafo.

{{:klauko:saida.png|}}

Para escrever o algoritmo de busca em nível de maneira elegante, usaremos uma estrutura de fila. Uma fila, do ponto de vista computacional,segue o mesmo conceito de uma fila tradicional de supermercado. Um novo consumidor entra no fina da fila e, à medida que os consumidores são atendidos, eles saem da frente da fila. A inclusão de um elemento no final de uma fila é chamada de **inserção** e a saída da frente da fila é uma operação de  **retirada**. Sendo assim, a notação //inserir(a,**F**)//  denota a inclusão do elemento //a// ao final da fila denominada **F**, e //retirar(a,**F**)// denota a retirada do elemento atual na frente da fila. Usaremos uma função //frente(**F**)//, cujo resultado é o valor do elemento atualmente na fila mas que não remove esse elemento. No algoritmo abaixo, os dados de entrada consistem em um grafo simples e conexo G, e um nó especificado //a//; a saída é uma lista de todos os nós em G em ordem de nível a partir de //a//.

<code C>
BuscaEmNivel(Graph G, node a)
{
   Inicialize F como sendo vazio;
   Marque a como tendo sido visitado;
   printf(a);
   inserir(a,F);
   while(F != vazio)
   {
     for(para casa nó n adjacente a frente(F))
     {
        if(n não visitado)
        {
           marque n como tendo sido visitado;
           printf(n);
           inserir(n,F);
        }//fim-do-se
     }//fim-do-para
     retirar(F);
   }//fim-do-enquanto
}//fim BuscaEmNivel
</code>