Implemente o algoritmo de Prim para encontrar uma árvore geradora de custo mínimo ( Algoritmo 8.1) de um grafo G = (V, E, W) dado.

ENTRADA: Grafo não-direcionado G = (V, E, W) com peso w definido para cada aresta.

SAÍDA: Árvore geradora de custo mínimo de G.

2. (Estude as páginas 367 a 412 do livro de Sara Baase.)

Implemente o algoritmo de Dijkstra para, dado um grafo G = (V, E, W), encontrar o menor caminho entre v e os demais vértices do grafo. Em seguida, para cada vértice w em G, imprima a seqüência de vértices que constitui o caminho de v até w.
IMPORTANTE: A operação de minimalização deve ser implementada usando um heap.

ENTRADA: Grafo não-direcionado G = (V, E, W) com peso w definido para cada aresta.

SAÍDA: Uma lista com todos os vértices w de G, com o respectivo caminho mais curto entre v e w.

3. Implemente uma modificação do Algoritmo Minimum_Edit_Distance, da página 158 do Manber,
para dadas duas cadeias de caracteres A e B, de n e m caracteres, respectivamente,
dizer qual o custo mínimo de edição e quais os passos para transformar a cadeia A na
cadeia B com este custo.

4. A maior subseqüência comum de duas seqüências T e P é a maior seqüência L que é simultaneamente uma subseqüência de T e de P.
A menor superseqüência comum de duas seqüências T e P é a menor seqüência L tal que
ambas, T e P, são subseqüências de L.

Escreva um programa eficiente para encontrar:

• A maior subseqüência comum de duas seqüências T e P, e
• A menor superseqüência comum de duas seqüências T e P.