Grafos

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 trabalho consiste 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 uma referê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 elemento armazenado 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 manipulado