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.

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.

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