Neste trabalho prático, vamos colocar em prática os conhecimentos sobre grafos aprendidos durante a disciplina. O projeto pode ser feito nas linguagens: c, c++ ou Java (qualquer outra linguagem desejada, deve ser conversada com o professor). Tanto a escolha da linguagem quanto as escolhas referentes ao código são de responsabilidades do grupo.
- Etapa 1 - (3 pontos) O trabalho consiste em ler o arquivo disponibilizado no Canvas que
contém dados referentes às latitudes e longitudes de algumas cidades brasileiras (você pode
escolher ler: CSV ou JSON).
Após a leitura desses dados, o programa deve ser capaz de gerar um grafo não direcionado e
ponderado que represente esse contexto, considerando os vértices como as cidades brasileiras
(presentes no arquivo) e as arestas como as rotas entre essas cidades, cujo peso é a distância da
rota.
Informação Importante: para cada cidade criada (vértice), considere que ela possua
ligações (arestas) somente com as três cidades mais próximas a ela. Essa característica irá deixar o
nosso grafo um pouco fora do contexto real, porém será importante para testarmos diferentes
alternativas nos algoritmos que serão criados nas próximas etapas.
Como o arquivo contém latitudes e longitudes, fica como responsabilidade do grupo procurar
como encontrar distância entre diferentes latitudes e longitudes, bem como desenvolver o programa
responsável por encontrar essa distância e definir quais arestas serão criadas.
- Entregáveis etapa 1: código para leitura do arquivo e criação do grafo.
- Etapa 2 - (3 pontos) Para percorrer esse grafo e escrever os dados referentes a ele,
implemente os métodos de busca em largura ou busca em profundidade (escolha entre uma das
duas buscas).
Posteriormente, deve-se implementar métodos capazes de receber como entrada um vértice
de origem e um vértice intermediário e, a partir desses, determinar um ciclo (se possível) que
comece e termine no vértice de origem e passe pelo vértice intermediário. Caso não seja possível, o
programa deve informar que não existe ciclo conforme solicitado.
Pontifícia Universidade Católica de Minas Gerais
Instituto de Ciências Exatas e Informática
Teoria dos Grafos | Prof. Felipe Soares
- Entregáveis etapa 2: Etapa 1 + código para busca em largura ou busca em profundidade e definição do ciclo.
- Etapa 3 - (9 pontos) Por fim, nessa última etapa, o grupo deve implementar um método que
recebe como entrada um vértice de origem e um vértice de destino e, a partir desses dados,
encontre o caminho mínimo para sair da origem e chegar ao destino.
Parte escrita - Deve ser entregue um artigo (usando LaTeX - utilizar “SBC Conferences
Template”) como resultado da realização deste trabalho prático (máximo 10 páginas). Anexo a esse
artigo deve ser entregue o projeto (códigos) do sistema desenvolvido (formato .zip). Esse artigo deve
conter a seguinte estrutura:
- Título
- Resumo
- Introdução
- Desenvolvimento
- Testes e Resultados
- Conclusão
- Referências
O artigo deverá conter as principais decisões adotadas sobre a estrutura de dados, os algoritmos utilizados para resolver o problema e exemplos de resultados obtidos. Caso se aproveite ou se adapte algoritmos disponíveis gratuitamente, a fonte deverá ser citada nas referências bibliográficas e o texto deverá explicitar as mudanças que foram necessárias.
- Entregáveis etapa 3: Etapa 1 + Etapa 2 + código para caminho mínimo + artigo documentando todo o trabalho realizado