IF672 - Algoritmos e Estruturas de Dados
novembro 2002 a março 2003

1 - Largura vs. Profundidade Trivial

 
 
Percorrer um grafo em largura e em profundidade.



Entrada e Saída de dados

A entrada consiste em vários conjuntos de dados.
Cada conjunto começa com um valor (N < 30) indicando a quantidade de nós no grafo direcionado.
Segue N linhas cada uma com a lista de adjacência correspondente ao nó i (i-ézima linha).
O final da linha de adjacência termina com 0.
Fim de arquivo indica o final da entrada.
A saída consiste da impressão da ordem de visitas dos nós na busca
em profundidade e na busca em largura (primeiro largura, depois profundidade).

NOTA: Priorize sempre os primeiros vértices de cada lista de adjacência.
              Comece a busca a partir do vértice 1.
              É possível que não se possa atingir todos os vértices do grafo
             (dizemos que grafos com essa propriedade são não-conectados ).


Entrada exemplo

 
5
2 4 3 0
1 0
4 5 0
1 3 0
1 2 3 4 0

3
2 3 0
1 3 0
1 2 0

6
2 3 0
1 4 0
1 2 4 0
1 2 3 0
6 0
5 0

Saída correspondente 

1 2 4 3 5
1 2 4 3 5

1 2 3
1 2 3

1 2 3 4
1 2 4 3