MAPA - ESTRUTURA DE DADOS I - 2021 B
A ANTT (Agência Nacional de Transportes Terrestres) concedeu a empresa rodoviária Bluginautorização de funcionamento para os 5 (cinco) destinos ilustrados pela figura a seguir:
Porém, devido a pandemia em 2020 e parte de 2021, a empresa vai diminuir esses destinos, passando a operar os destinos que representam o menor custo organizacional.
No contexto da figura, os vértices 1, 2, 3, 4 e 5 representam, respectivamente, as cidades que a companhia rodoviária opera hoje. O trajeto é representado pelas arestas que liga (1 a 2), (1 a 3), (2 a 3), (2 a 5), e assim por diante.
O custo (peso) entre cada conexão está representado por 2. Porém, de fato, o valor real do custo são os 7 primeiros dígitos do seu RA multiplicado por 100, na sequência: (1-2), (1-3), (2-3), (2-5), (3-4), (3-5), (4-5).
Exemplo:
RA 2025703-5 = Utilizar 2025703
RA 202570-5 = Em caso de 6 digitos, acrescentar o digito 1, neste exemplo teremos 2025701
Considerando o contexto apresentado da empresa rodoviária Blugin Tur, imagine que você é um desenvolvedor da empresa e ficou responsável por elaborar o caminho de menor custo saindo da cidade 1 e chegando na cidade 5. Para atender a esta demanda Você decidiu utilizar o algoritmo de Dijkstra, para indicar os destinos que continuarão sendo operados pela companhia o seu respectivo peso.
Passos para realizar o mapa:
1 - Desenvolva um programa em linguagem C e salve com a extensão (.c) que informe os caminhos saindo de 1 e chegando em 5.
1.1 - Neste código, você deverá informar:
- o número de vértices,
- depois a aresta de origem, a aresta de destino, e
- o custo correspondente aos digitos de seu RA para as rotas (lembre-se que após Digitar o custo, temos uma operação a ser realizada).
1.2 - Imprimir todos os destinos com os seus respectivos pesos.
2 - Após a impressão (item 1.2) tirar um print da sua tela de forma que pegue todos os destinos.
- Neste print marque o (s) caminho (s) de menor custo saindo de 1 e chegando Em 5.
- Salve com extensão (.doc), (.docx), (.pdf), (.png) e (.jpg).
* Como entregar a atividade:
Compacte código fonte em linguagem C (item 1) junto com o arquivo (item 2), e anexe no ambiente da Atividade (no STUDEO).
ATENÇÃO: revise com bastante atenção a sua atividade antes de postá-la no ambiente. Verifique se não esqueceu nada, se é o arquivo correto, se está no formato correto, etc. Após o envio não serão permitidas alterações.
Durante a disciplina, procure sanar suas dúvidas pontuais em relação ao conteúdo relacionado a atividade.
Porém, não são permitidas correções parciais, ou seja, enviar para que o professor possa fazer uma avaliação previa e retornar para que o aluno possa ajustar e enviar novamente. Isso não é permitido, pois descaracteriza o processo de avaliação.
Por favor, não insista!!!
Soluções para a tarefa
Grafo simples é um grafo não direcionado, sem laços e existe no máximo uma aresta entre quaisquer dois vértices (sem arestas paralelas). Para um grafo simples, o número de vizinhos de um vértice é igual à sua valência.
Grafo completo é o grafo simples em que, para cada vértice do grafo, existe uma aresta conectando este vértice a cada um dos demais. Ou seja, todos os vértices do grafo possuem mesmo grau. O grafo completo de n vértices é frequentemente denotado por Kn. Ele tem n(n-1)/2 arestas (correspondendo a todas as possíveis escolhas de pares de vértices).
Grafo nulo é o grafo cujo conjunto de vértices é vazio.
Grafo vazio é o grafo cujo conjunto de arestas é vazio.
Grafo trivial é o grafo que possui apenas um vértice e nenhuma aresta.
Grafo regular é um grafo em que todos os vértices tem o mesmo grau.
Multigrafo é um grafo que permite múltiplas arestas ligando os mesmos vértices (arestas paralelas).
Pseudografo é um grafo que contém arestas paralelas e laços.
Grafo conexo um grafo é conexo se for possível estabelecer um caminho de qualquer vértice para qualquer outro vértice de um grafo. Se for sempre possível estabelecer um caminho de qualquer vértice para qualquer outro vértice mesmo depois de remover k-1 vértices, então diz-se que o grafo está k-conexo. Note que um grafo está k-conexo se, e somente se, contém k caminhos independentes entre qualquer par de vértices. O grafo de exemplo acima é conexo (e portanto 1-conexo), mas não é 2-conexo. Em um grafo genérico G, o corte associado a um conjunto X de vértices é o conjunto de todas as arestas que têm uma ponta em X e outra em V(G) - X, onde V(G) é o conjunto de todos os vértices pertencentes ao grafo G.
Ponto de articulação ou Vértice de corte é um vértice cuja remoção desliga um grafo. Uma ponte é uma aresta cuja remoção desliga um grafo. Um componente biconectado é um conjunto máximo de arestas tal que qualquer par de arestas do conjunto fazem parte de um ciclo simples comum. O contorno de um grafo é o comprimento do ciclo simples mais curto no grafo. O contorno de um grafo acíclico é, por definição, infinito.
Árvore é um grafo simples acíclico e conexo. Às vezes, um vértice da árvore é distinto e chamado de raiz. As árvores são muito usadas como estruturas de dados em informática (veja estrutura de dados em árvore).
Floresta é um conjunto de árvores; equivalentemente a uma floresta, em algum grafo acíclico.
Subgrafo de um grafo G é um grafo cujo conjunto dos vértices é um subconjunto do conjunto de vértices G, cujo conjunto de arestas é um subconjunto do conjunto de arestas de G, e cuja função w é uma restrição da função de G
Subgrafo gerador é aquele obtido pela remoção de uma ou mais arestas de um outro grafo, dizemos então que este novo grafo obtido é gerador do primeiro,
Nosso primeiro passo, depois de definirmos o escopo do grafo é cria-lo, para isto receberemos de parâmetro a variável v que representa o numero de vértices que o grafo possui.
Quando entramos na função, ela é de simples entendimento: Reservamos um espaço na memória (linha 39), dizemos que o numero de vértices é igual o da variável o informado (linha 40), deixamos o numero de arestas zerados, pois ainda não criamos nenhuma.
A parte mais não intuitiva é a linha 40. Nela aloco o arranjo contendo os v vértices na memória, note que a adj não é o arranjo em sim, mas sim um ponteiro que aponta para o arranjo.
Infelizmente os compiladores C colocam valores aleatórios na memória quando eles alocam, para não ficar estes valores(lixo), criamos um for (linha 44 a 46) em que colocamos um valor nulo em todos ponteiros, para assim ficar um grafo recém criado sem nenhum valor em nenhum ponteiro, ou seja, grafo sem nenhuma adjacência.