INF1010 - Grafos - Percursos em Grafos: Profundidade e Largura

entrega: até sábado, dia 2/11, à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. Assuma que os grafos percorridos são conectados, isto é, sempre existe um caminho entre quaisquer dois vértices.

1. 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.
2. (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, você 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. (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.

4. (3,5 pontos) Implemente novamente outra versão da funçã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.

Extra: Que modificações você deve fazer para que seja possível percorrer também grafos que não sejam conectados? (Não é necessário implementar, apenas indique as modificações necessárias em seu código)

Atenção: Indique na área de texto da tarefa quais funções você implementou e testou, e copie e cole a saída do teste final, independentemente do número de funções que vc tiver implementado!