Grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1666 palavras )
  • Download(s) : 0
  • Publicado : 11 de abril de 2012
Ler documento completo
Amostra do texto
Universidade de São Paulo
Instituto de Ciências Matemáticas e de Computação
Departamento de Ciências de Computação
SCC-203 – Algoritmos e Estruturas de Dados II / 2011
Prof.ª Rosane Minghim

Trabalho 1 – GRAFOS
O problema do caminho mínimo consiste em encontrar o caminho de menor custo que
começa em um vértice o e termina em um vértice d. Uma vez definido tal problema, o presente
trabalhoconsiste em:
1. Implementar uma Estrutura de Dados Dinâmica para grafos não-direcionados, na
forma de lista de adjacências.
2. Usar a estrutura de dados implementada para implementar um TAD Grafo. Seu TAD
deve possuir necessariamente o seguinte conjunto mínimo de operações (funções)1:
 endVertices(G, e): retorna referências para os dois vértices finais da aresta e.
 opposite(G, v, e): retorna umareferência para o vértice oposto a v na aresta e.
 areAdjacent(G, v, w): verdadeiro se os vértices v e w forem adjacentes, falso caso
contrário.
 replaceEdge(G, e, o): substitui o elemento da aresta e por o.
 replaceVertex(G, v, o): substitui o elemento do vértice v por o.
 insertVertex(G, o): insere um novo vértice isolado, armazenando nele o elemento o,
e retorna uma referência para esse vértice. insertEdge(G, v, w, o): insere uma aresta (v,w), armazenando nela o elemento o, e
retorna uma referência para essa aresta.
 removeVertex(G, v): remove o vértice v (e suas arestas) e retorna o elemento
armazenado nele.
 removeEdge(G, e): remove a aresta e, retornando o elemento armazenado nela.
 edgeValue(G, e): retorna o elemento armazenado na aresta e.
 vertexValue(G, v): retorna o elementoarmazenado no vértice v.
3. Implementar uma rotina chamada Dijkstra(G, o, d) que determina o menor caminho
(caminho mínimo) entre o vértice o de origem e o vértice d de destino do grafo G. Ao
final da execução da rotina, seu programa deve imprimir na tela o caminho mínimo
que leva de o até d, bem como seu custo, como será especificado adiante.
 Entrada e Saída de Dados
O grafo a ser manipuladoserá especificado ao seu programa a partir da entrada de dados
padrão (teclado). Para isso, implemente um procedimento que leia dados a partir do teclado e
utilize as funções do seu TAD Grafo para construir e armazenar o grafo correspondente. O número
máximo de vértices que seu programa deve tratar é igual a 100. O número máximo de arestas é
igual a 200.
Os comandos permitidos para operar sobre seuTAD são representados por duas letras
maiúsculas. Toda linha de entrada obrigatoriamente inicia com um comando. Só serão fornecidos
como entrada comandos aqui especificados (não há necessidade de tratar comandos inválidos, pois
1

Notas: (i) Tanto arestas quanto vértices devem armazenar elementos com valores inteiros positivos; (ii) As
“referências” a vértices e arestas são ponteiros para osrespectivos nós das listas de arestas e vértices.

só serão fornecidos comandos válidos). Os únicos comandos permitidos como entrada são
apresentados a seguir. O símbolo ¶ denota um único espaço em branco.
1. Cria vértice
CV ¶ x
CV cria um vértice contendo o valor x.
Vértices só armazenarão números inteiros
positivos.

4. Deleta aresta
DA ¶ u
DA deleta a aresta de identificador u. Não
serão fornecidosidentificadores de arestas
inexistentes.

2. Deleta vértice
DV ¶ v
DV deleta o vértice identificado por v (veja
abaixo a nota a respeito de identificadores).
Não serão fornecidos como entrada
identificadores inexistentes.

5. Troca valor do vértice
TV ¶ v ¶ x
TV troca o valor armazenado no vértice de
identificador v pelo valor x. Não serão
fornecidos
identificadores
de
vértices
inexistentes.

3.Cria aresta
CA ¶ v1 ¶ v2 ¶ x
CA cria uma aresta entre os vértices de
identificador v1 e v2. O valor armazenado na
aresta é um número inteiro especificado por x.
Não serão fornecidos identificadores de
vértices inexistentes.

6. Troca valor da aresta
TA ¶ u ¶ x
TA troca o valor armazenado na aresta de
identificador u pelo valor x. Não serão
fornecidos
identificadores
de
arestas
inexistentes....
tracking img