Trabalho alpro 3

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 [e-mail]; [e-mail]

Abstract. 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 o a - 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 foi utilizada 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.