Trabalho alpro 3

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1434 palavras )
  • Download(s) : 0
  • Publicado : 25 de junho de 2012
Ler documento completo
Amostra do texto
Trabalho de Grafos da disciplina de Algoritmos e Programacao 3 ¸˜
Rafael B, Thiago de
1

Pontif´cia Universidade Cat´ lica do Rio Grande do Sul (PUCRS) ı o Porto Alegre – RS – Brazil
2

Curso de Sistemas de Informacao – PUCRS. ¸˜
3

Faculdade de Inform´ tica - FACIN a Pontif´cia Universidade Cat´ lica do RS (PUCRS) ı o
rafael.rodrigues.004@acad.pucrs.br; thiago.lucca@acad.pucrs.brAbstract. Este artigo descreve a solucao para os problemas propostos no tra¸˜ balho sobre arvore geneal´ gica da disciplina de Algoritmos e Programacao 3 o ¸˜ ´ que trata do desenvolvimento de trˆ s algoritmos em linguagem de programacao e ¸˜ C ou java. As solucoes s˜ o apresentadas com os devidos tempos e resultados. ¸˜ a Ao final apresentamos os problemas enfrentados no desenvolvimento,complexidade e a conclus˜ o do artigo. a

1. Introducao ¸˜
´ O objetivo deste artigo e demonstrar os resultados obtidos dos algoritmos desenvolvidos, para resolver as quest˜ es propostas pelo presente trabalho. O qual trata-se de responder o trˆ s quest˜ es abaixo relacionadas. Foram fornecidas listas que cont´ m os nomes dos e o e personagens da odiss´ ia, as quest˜ es solicitadas s˜ o as seguintes: e oa - Dados dois personagens mitol´ gicos ’r’ e ’s’, deseja-se saber qual o ancestral o mais pr´ ximo dos dois? o ´ - Qual a altura da arvore e quantos personagens est˜ o abaixo de um dado personaa gem ’p’? ´ ´ - E a ultima quest˜ o solicitada e apresentar o caminho mais longo composto apea nas por nomes que iniciam com vogais, e tamb´ m por consoantes. e No desenvolvimento das atividades foiutilizada a linguagem Java onde foram usadas as seguintes estruturas de dados: grafos, List, ArrayList e matriz. O algoritmo segue a seguinte ordem de funcionamento: ´ 1. O arquivo com os nomes e carregada para a estrutura do grafo; 2. A primeira linha do arquivo informa a quantidade de arestas que o grafo possui. 3. Ap´ s o carregamento um dos m´ todos adiciona cada nome a um v´ rtice do o e e grafo.4. No passo seguinte estes v´ rtices s˜ o ligados por arestas respeitando a ordem do e a ´ ´ arquivo informado que e: primeiro nome da linha e o ancestral do segundo nome. ´ 5. O grafo utiliza uma matriz de adjacˆ ncias que cont´ m n v´ rtices, e uma matriz e e e n x n de bits.

´ 6. Quando a estrutura do grafo est´ montada e com os dados carregados, e exea cutado o primeiro algoritmo, de buscado ancestral, que deveria ser retornado em uma vari´ vel. a 7. O segundo algoritmo consiste em informar a altura de determinado v´ rtice e abaixo de um dado personagem, retornando o resultado em uma vari´ vel. a ´ 8. O ultimo algoritmo ap´ s sua execucao deveria informar o maior caminho entre o ¸˜ os v´ rtices cujos nomes comecem com vogais e tamb´ m o maior caminho entre os v´ rtices e e e quepossuem nomes que comecam com consoantes (foi utilizado o algoritmo de busca em ¸ profundidade, visto que n˜ o conseguimos desenvolver o algoritmo solicitado. a Ap´ s a leitura e interpretacao do problema, foi executada a estruturacao das claso ¸˜ ¸˜ ses que ficou da seguinte forma: - Classe Start, que inicia o programa e carrega os dados do arquivo, instancia um grafo e insere os v´ rtices earestas, por fim a classe chama os m´ todos para execucao e e ¸˜ ´ dos algoritmos solicitados. Esta classe tamb´ m possui um “contador” de tempo, que e e utilizado para registrar o tempo de cada algoritmo. - Classe Grafo, cont´ m as estruturas de dados usadas bem como os m´ todos para e e instanciar um novo grafo, inserir v´ rtices, arestas, percorrer o grafo em altura e lare gura, marcacao/desmarcacaodos v´ rtices e por fim um m´ todo que tem como sa´da os ¸˜ ¸˜ e e ı parˆ metros do grafo, utilizados em outra aplicacao que “desenha” o referido grafo. a ¸˜ Nos par´ grafos seguintes s˜ o exibidos os resultados dos casos de teste executados, a a bem como o desenho do grafo do primeiro caso de teste, gerado pela aplicacao Graphviz. ¸˜ Grafo gerado pelo programa, caso de teste usado: caso6.

2....
tracking img