Trabalho Prático I da disciplina de Grafos.
1 - Implementar a representação computacional de Matriz de Adjacência e de Lista de Adjacência para a representação computacional de grafos e dígrafos. Atenção: todos os algoritmos implementados devem ser executados com qualquer um desses dois tipos de representação computacional de grafos. O seu programa deve disponibilizar para o usuário, na interface, a opção de escolher com qual representação ele irá trabalhar.
2 – Implementar a busca em profundidade para ser executada a partir de um nó raiz fornecido pelo usuário. Em seguida, exibir o tempo de chegada (cinza) e o tempo de finalização (preto) de cada vértice. Note que o vértice inicial é escolhido pelo usuário, mas a busca em profundidade varrerá todo o grafo (ou dígrafo).
3 – Implementar a busca em largura. O usuário deve fornecer o nó raiz para iniciar a busca em largura. Após a busca ser realizada, exibir o caminho percorrido para chegar em cada vértice do grafo e o tamanho do caminho (distância até a raiz). Para isso, utilize as estruturas auxiliares empregadas pela busca em largura.
4 – Implementar a verificação de um caminho entre dois vértices u e v. O usuário indicará quais são esses vértices e escolherá entre a busca em profundidade e a busca em largura para verificar a existência desse caminho. Se existir o caminho entre u e v, o programa deverá exibir esse caminho; caso contrário, o programa dever informar que não há um caminho entre os vértices indicados.
5 – Implementar uma função para verificar se um grafo é conexo. Se ele não for conexo, deve ser apresentado o número de componentes conexas que formam o grafo. Exiba a qual componente cada vértice pertence. Note que esse exercício é só para grafo.
6 – Fazer um programa que implemente os algoritmos de Prim e de Kruskal para computar uma árvore geradora mínima em grafos ponderados. Note que esse exercício é só para grafo.
7 – Fazer um programa que implemente os algoritmos de Dijkstra e de Bellman-Ford para encontrar o caminho mínimo a partir de um vértice inicial escolhido pelo usuário. Após a execução, o programa deverá exibir o caminho mínimo desse vértice para todos os outros vértices do grafo e também a distância. Esse algoritmo deverá ser implementado para dígrafos ou grafos ponderados.