Algoritmo de Prim para Árvore Mínima

Prévia do material em texto

Árvore de Prim
Uma árvore é um grafo conexo sem ciclo. Ou seja, deprezando-se a orientação das
arestas, ao partirmos de um vértice qualquer é impossível retornar a ele sem repetirmos aresta.
Numa árvore G = (V, A) sempre | V | = | A | + 1 (ou simplesmente V = A + 1 como “abuso de
notação”). Dado um grafo conectado, o Algoritmo de Prim ajuda a encontrar quais arestas
redundantes podem ser retiradas para que todos os nós ainda continuem conectados
através de uma árvore com custo mínimo. A seguir, vamos apresentar uma versão
simplificada do Algoritmo de Prim usando como exemplo o grafo da Figura 2.
Figura 2 - Exemplo de grafo conectado para aplicação do Algoritmo de Prim 
Dado um nó de origem, digamos o nó v1 do grafo da Figura 2, o Algoritmo de Prim escolhe a menor aresta
associada a este nó (aresta com valor 2) e, a seguir, inclui o nó v2 dentre os nós já descobertos. Agora o
algoritmo considera qual das arestas partindo de v1 ou v2 tem o menor valor (neste caso, a aresta de
valor 1, partindo de v2), e assim sucessiva-mente. O grafo da Figura 3 mostra o resultado da aplicação
do Algoritmo de Prim no grafo da Figura 2.
Figura 3 - Árvore mínima após a aplicação do Algoritmo de Prim.