Árvore Geradora Mínima

A árvore geradora mínima de um grafo, também conhecida como árvore de extensão mínima, ou árvore de extensão de peso mínimo, é uma árvore que conecta todos os vértices de um grafo ponderado não direcionado, de forma que a soma de todos os pesos das arestas da árvore é a menor possível, para o grafo em questão.

Entre as aplicações para a árvore geradora mínima, está a interconexão de redes Ethernet para broadcasting (utilizando o protocolo STP - Spaning Tree Protocol), redução do custo de obras de infraestrutura, onde o objetivo é ligar vários pontos (por exemplo: metrô, fibra ótica, saneamento), ou até mesmo registo de imagens.

O primeiro algoritmo para encontrar uma árvore geradora mínima foi desenvolvido por Otakar Borůvka em 1926, seguido pelo algoritmo de Prim (Jarník, 1930), e pelo algoritmo de Kruskal (1956).

Algoritmo de Prim

O algoritmo de Prim encontra a árvore geradora mínima de um grafo ponderado e não-direcionado, cujo custo computacional é de $O(V^2)$ (sendo V o número de vértices), quando o grafo é representado por uma matriz de adjacências, ou $O(E \log V)$ (sendo E o número de arestas), quando o grafo utiliza filas de prioridades para armazenar as arestas. É um algoritmo guloso, ou seja, busca a resposta global a partir da melhor opção local.

Desenvolvido em 1930 pelo matemático tcheco Vojětch Jarník, este algoritmo foi redescoberto por Robert Prim em 1957, e por Edsger W. Dijkstra, em 1959, e por isso também é conhecido com algoritmo de Jarník, algoritmo de Prim-Jarník, ou algoritmo de Prim-Dijkstra.

Em sua forma básica (Algoritmo 1), o algoritmo encontra apenas uma árvore geradora mínima em um grafo conexo. Quando aplicado a um grafo desconexo, é possível aplicar o algoritmo repetidas vezes (Algoritmo 2), nos vértices restantes, e obter, assim, uma Floresta Geradora Mínima. Alguns algoritmos, como o de Kruskal ou o de Borůvka, obtém a floresta geradora mínima em uma única aplicação dos algoritmos.

Pseudo-código para o Algoritmo de Prim

A partir de um vértice V, que representa a raiz da árvore T,
Enquanto houverem conexões entre a arvore T e o grafo G:
    Retire do grafo G o vértice U ligado a árvore T pela aresta E de menor custo.
    Adicione o vértice U à árvore T, ligando-o pela aresta E.
    Remova todas as arestas que ligam a árvore T a ela mesma.

Para grafos esparsos, os algoritmos são equvalentes em relação ao tempo de execução, no entanto, para grafos densos, o algoritmo de Prim pode ser modificado para executar em tempo linear.

Modificação para a Floresta Geradora Mínima

Enquanto houverem vértices no grafo G:
    Retira um vértice V do grafo G adicionando-a a floresta F como uma nova raiz.
    Executa o algoritmo básico de Prim utilizando V como a nova raíz.