INF1010 - Grafos - Percursos em Grafos: Profundidade e Largura
entrega: até sexta, dia 7/6, às 23h
O arquivo grafo.c contém um esboço
de implementação de grafos usando listas encadeadas para representar
arestas e mais umas funções auxiliares.
A interface está em grafo.h e os
arquivos grafo1.dat
e grafo2.dat.
contêm dois grafos no formato esperado por grafoLe.
No laboratório de hoje vamos implementar os percursos em
profundidade e largura usando essa representação.
- Compile e execute o teste
em testeGrafo.c.
O teste exibe o grafo lido e depois pede nós de partida.
Ignore essa segunda parte inicialmente (entre com -1 nas duas
perguntas).
Certifique-se (com papel e lápis) que você entendeu o que está
sendo mostrado na tela.
-
(3 pontos)
Implemente usando recursão a função grafoPercorreProfundidade que visita
os nós de um grafo a partir de um nó dado usando o conceito de visita em profundidade.
A visita em si é bem boba, apenas imprime o número do nó.
Para implementar essa função e as seguintes, vc precisa de uma maneira de marcar
os nós já visitados.
Por isso, recomendo que use uma função invólucro (wrapper) que
crie a estrutura de marcação e passe-a para uma função recursiva interna.
-
(3,5 pontos)
Implemente a função grafoPercorreLargura que visita
os nós de um grafo a partir de um nó dado usando o conceito de visita em largura.
Uma maneira comum (não recursiva) de implementar a busca em largura é
criarmos uma fila dos nós a serem visitados, como discutido em sala.
Inicialmente essa fila contém apenas o nó origem do percurso.
O algoritmo seguidamente retira nós dessa fila para visitá-los.
Para cada nó, percorre-se a lista de vizinhos, enfileirando aqueles
que ainda não foram enfileirados até então.
(atenção aqui! em vez de marcar quem já foi visitado, como no percurso
em profundidade,
é melhor marcar quem já foi enfileirado!)
O percurso termina quando não há mais itens na fila.
As funções newList, enqueue e dequeue
do arquivo esqueleto já estão
prontas para vc implementar sua fila de nós a serem visitados.
- (3,5 pontos)
Implemente novamente outra versão dafunção grafoPercorreProfundidade sem usar
recursão.
Chame-a de grafoPercorreProfundidade2.
Para isso, em vez de fazer chamadas recursivas vc pode colocar os nós a serem visitados
em uma pilha.
As funções push e pop implementam as operações auxiliares para manter
a pilha.