Instruções para Construção de Grafo na 3ª Unidade

IMPORTANTE Instruções extras para 3a Unidade IMPORTANTE Instruções extras para 3a Unidade 1 12 Sobre a questão única A atividade deve ser respondida de acordo com o que descreve o roteiro ou seja a QUESTÃO ÚNICA deve ser minimamente respondida Para isto as instruções na sala de aula sobre grafos serão de extrema importância para o desenvolvimento do trabalho Mas para iluminar o entendimento de como começar a construção do grafo vou apresentar a construção de um grafo simples IMPORTANTE Instruções extras para 3a Unidade 2 12 Estruturas já criadas As estruturas iniciais podem ser as próprias definidas no trabalho de Hash struct cidade unsigned int id char estado char cidade struct gps unsigned int id latitude la longitude lo struct dataItem int key cidade city gps GPS IMPORTANTE Instruções extras para 3a Unidade 3 12 Captura de dados Observe que para a Hash os valores poderiam ser estruturados simplesmente pelos dataItems O próprio arquivo lerArquivoscpp ensina como podemos extrair os valores das cidades presentes nos arquivos coordenacaocsv e cidadescsv que estão presentes no perfil do github do professor Atenção Verificar se o código está funcionando adequadamente para as necessidades suas talvez os nomes dos arquivos estejam diferentes nos projetos Projeto HashTable e Projeto Grafo IMPORTANTE Instruções extras para 3a Unidade 4 12 Captura de dados Mais precisamente as funções abaixo conseguem capturar os dados das cidades nestes arquivos dataItem getItenscidade gps cidade getCidadeschar arquivo gps getGpschar Utilizando a função dataItem por exemplo vocês tem acesso a todas as cidades que estão no arquivo Já que dataItem é formado por uma chave a estrutura da cidade e localização da cidade IMPORTANTE Instruções extras para 3a Unidade 5 12 Captura de dados Vou aqui agora apresentar como construir um grafo a partir das cidades dos arquivos cidade todasCidades getCidadescharbancoDeDadoscidadescsv gps todoLocal getGpscharbancoDeDadoscoordenadascsv dataItem d getItenstodasCidades todoLocal Selecionando as cidades do RN int k0 dataItem cidadesDoRN dataItemmalloc167sizeofdataItem gps localRN gpsmalloc167sizeofgps forint i 0 i5570 i if comparar todasCidadesicidadeestado RN 0 cidadesDoRNk todasCidadesi localRNk todoLocali k IMPORTANTE Instruções extras para 3a Unidade 6 12 Captura de dados Depois desse passo teremos no vetor cidadesDoRN os valores de todas as cidades do estado do RN Feito isso podemos calcular a distância entre cada par de cidades da seguinte maneira Um exemplo abaixo comparo a distância entre a cidade 5 e a cidade 10 com a distância de 005 float d distancialocalRN5 localRN10 ifd 005 São vizinhas G510 d G105 d IMPORTANTE Instruções extras para 3a Unidade 7 12 Construção do Grafo Veja que o grafo simplesmente é a matriz G Que pode ser definida da seguinte maneira float G167167 IMPORTANTE Instruções extras para 3a Unidade 8 12 Construção do Grafo A representação do grafo que considero mais simples avalia simplesmente os valores de G Neste caso estaremos construindo um Grafo com n 167 vértices e no máximo nn1 2 13861 arestas Este grafo é não orientado simétrico e ponderado Os pesos representam simplesmente a distância entre os centros das cidades informações no arquivo coordenadacsv IMPORTANTE Instruções extras para 3a Unidade 9 12 Entrega dos resultados Para concluir e facilitar a entrega da atividade solicito que preencham as tabelas abaixo abaixo e coloquem esses resultados em um arquivo dos seus repositorios com o nome resultadosmd Tabela 1 Dist Cid mais viz Qnt Cid menos viz Qnt 005 010 020 025 Ou seja indiquem qual a cidade com mais e menos vizinhos e a quantidade de vizinhos IMPORTANTE Instruções extras para 3a Unidade 10 12 Entrega dos resultados Tabela 2 Distancia Máx Min Sendo Máx A menor distância possível para que todas as cidades do RN seja consideradas vizinhas Min A maior distância possível para que nenhuma cidade seja considerada vizinha IMPORTANTE Instruções extras para 3a Unidade 11 12 Entrega A entrega dos resultados será por grupo na quintafeira 2411 Na oportunidade algum integrante do grupo deverá aparecer para representar o grupo por completo e mostrar as execuções dos códigos e as conclusões apresentadas informações das tabelas preenchidas IMPORTANTE Instruções extras para 3a Unidade 12 12