IF096 - Algoritmos e Estruturas de Dados
 fevereiro a junho de 2000

Lista de Exercícios 3
Entrega: Quinta-feira, dia 18/maio, no início do horário da monitoria.

 

1. Escrever um procedimento linear para, dado um grafo conexo não direcionado G = (V, E) que contém exatamente um ciclo, direcionar as arestas deste grafo de forma que os graus de entrada de todos os vértices no grafo direcionado gerado na saída sejam no máximo 1.
Note que tudo o que é necessário fazer é identificar as arestas que compõem o ciclo, direcionando-as todas no mesmo sentido, enquanto as demais arestas devem ser direcionadas "de dentro para fora" do ciclo. Isso pode ser feito usando a pilha Q do algoritmo apresentado.

2. Modificar o procedimento da Fig. 7.17 do livro de Udi Manber para: Dado um grafo não direcionado simples G = (V, E) e um vértice v de V, identificar a última aresta que compõe um caminho mais curto de v para cada um dos vértices de G. Caso haja mais de um caminho possível, um caminho com o menor número de arestas deve ter preferência.
IMPORTANTE:
1. O custo do algoritmo modificado deve ser exatamente o mesmo custo do algoritmo na Fig. 7.17 referenciado.
2. A operação de minimalização deve ser implementada usando um heap.

3. Modificar o procedimento da Fig. 7.20 do livro de Udi Manber para: Dado um grafo não direcionado simples G = (V, E), imprimir as arestas que definem uma árvore geradora de peso mínimo de G.
IMPORTANTE:
A operação de minimalização deve ser implementada usando um heap.

Retorna à página principal do curso

[Última alteração em 02.maio.2000 por katia.]