Relatório Grafos

Prévia do material em texto

INSTITUTO FEDERAL DO ESPÍRITO SANTO
BACHARELADO EM SISTEMAS DE INFORMAÇÃO
ARTHUR DELPUPO E MATHEUS T. DE AGUIAR
TÉCNICAS DE PROGRAMAÇÃO AVANÇADA
Relatório referente ao primeiro envio do trabalho sobre grafos.
Serra - ES
2022
Introdução
Um grafo é uma estrutura de dados composta por nós e arestas, usada
comumente para representar a realidade, como por exemplo um sistema rodoviário
que liga cidades. Dentre as diversas formas para implementar um grafo, a
linguagem utilizada foi Java, fazendo uso do conceito de generics.
Foram apresentadas as seguintes formas de implementação dessa estrutura
de dados: Listas de Adjacências, Matriz de Adjacências e Listas de Arestas. Após
uma análise das três formas, levantando em consideração vantagens e
desvantagens atreladas a cada natureza de implementação, optamos por escolher
primeira forma, visto que consideramos a melhor forma de implementação, visto que
consiste na criação de um vetor para cada vértice, cujo esse vetor tem
conhecimento dos vértices conectados a ele. Ademais, é relevante frisar que o grafo
implementado era duplamente encadeado, conexo e, portanto, facilitando o
desenvolvimento.
Como fator decisivo à escolha, levamos em conta a sua facilidade de
implementação, todavia é a menos lógica dentre as demais, ao menos na visão do
nosso grupo. Ademais, dentre as soluções disponíveis, não era a mais eficiente,
visto que a forma utilizando matrizes é mais rápida na montagem e em tempo de
execução, bem como econômica. Apesar de em uma primeira análise a lista de
adjacências parecer confusa, depois de entendida esta forma se torna prática e
intuitiva.
Visando facilitar a compreensão da forma implementada, tomemos por
exemplo o seguinte grafo abaixo:
figura 1: exemplo ilustrativo de grafo genérico utilizado na implementação
A Lista de Adjacências
A lista de adjacências consiste em escrever para cada número de linha e
seus vértices que tem “conhecimento”, da seguinte maneira:
1. 2, 3
2. 1, 3, 4
3. 1, 2
4. 2, 5
5. 4
Em outra visão ficaria organizada da seguinte forma:
1 2 3 4 5
1 2 3
2 1 3 4
3 1 2
4 2 5
5 4
tabela 1: tabela representando a disposição dos vértices e arestas de um grafo genérico
A estrutura é composta por três classes genéricas, sendo elas: Grafo, Vértice
e Aresta.
● A classe vértice armazena o valor do vértice e também uma lista com os
destinos dos vértices.
● A classe aresta possui um objeto do tipo vértice e também armazena os
pesos (distância entre as arestas).
● A classe grafo armazena uma lista de vértices.
Conclusão
Sendo assim, de acordo com as informações previamente citadas, conclui-se
que os grafos são estruturas de dados muito importantes para a organização e
armazenamento de dados, existem diversas formas de implementação cada uma
delas possuindo suas vantagens e desvantagens. O trabalho agregou uma nova
ótica ao grupo quanto a essa estrutura de dados.