Enunciado 2a - Departamento de Matemática
Contents
1. Para mais facilmente efectuar testes deve ser estabelecido um formato apropriado para o armazenameto da estrutura do grafo num ficheiro O relat rio a escrever deve ter a seguinte estrutura geral e Identificar o trabalho e os seus autores e Descrever especificar o problema e Descrever a sua utiliza o manual do utilizador Apresenta o do Algoritmo implementado Apresenta o da Estrutura de Dados usada e Refer ncia a particularidades do programa se que as tem Em anexo deve se incluir e Listagem do programa e Exemplos de utiliza o do programa Refer ncias 1 Alfred Aho John Hopcroft and Jeffrey Ullman Data Structures and Algorithms Addison Wesley Publishing Company 1983 2 Sara Baase Computer Algorithms Introduction to Design and Analysis Addison Wesley Publishing Company 1983 3 A T Berztss Data Structures Theory and practice Academic Press 2nd edition 1975 4 Ellis Horowitz and Sartaj Sahni Fundamentals of Data Structures in Pascal Computer Science Press 19872. Departamento de Matem tica Universidade de Coimbra Ano Lectivo de 2002 2003 Algoritmos e Estruturas de Dados II Projecto 2a Com a defini o do Tipo Abstracto de Dados Digrafo 1 2 3 4 pretende se ter um tipo da dados que nos permita manipular Grafos Orientados Directed Graphs Um grafo pode ser representado atrav s de uma matriz de adjac ncias ou atrav s de uma lista de adjac ncias em ambos os casos trata se de representar o grafo atrav s dos seus n s e para cada um desses n s as suas adjac ncias Entre as opera es de manipula o de grafos b sicas temos adicionar um n adicionar um arco remover um n remover um arco verificar se um n uma lt fonte gt verificar se um n um lt po o gt e efectuar a coalesc ncia de dois n s adjacentes 1 Implemente em C o Tipo Abstracto de Dados DiGrafo utilizando para tal uma matriz de adjac n cias 2 Construa um programa em C que permita fazer algumas manipula es b sicas em grafos por utiliza o do TAD Digrafo nomeadamente e construir o grafo orientado atrav s da leitura de um ficheiro que contenha uma dada represen ta o do grafo e armazenar o grafo em ficheiro e modificar a estrutura do grafo e visualizar o grafo 3 Implemente eventualmente num programa em C separado o algoritmo de Dijkstra para o obten o do caminho mais curto tomando em considera o o n mero de arcos entre n s de um dado grafo 1 2 3 4
Download Pdf Manuals
Related Search