Análise de Algoritmos | Aulas | Dicionário | Índice

Algoritmo de Prim para o problema MST

Esta página trata do problema das árvores geradoras de peso mínimo em grafos. Trata-se de uma generalização do problema da árvore geradora discutido no capítulo Árvores geradoras de grafos. O problema desta página é conhecido pelas iniciais MST de minimum spanning tree. A página trata, em particular, do célebre algoritmo de Prim para o problema da MST.

Esta página é inspirada no capítulo 23 de CLRS.

Árvores geradoras de peso mínimo

Suponha que cada aresta vw de um grafo tem um peso (= weight) numérico f(vw), que pode ser positivo, negativo, ou nulo. Diremos que f é uma função-peso definida sobre os arestas do grafo. O peso de um sub­grafo T do grafo é a soma dos pesos das arestas de T e será denotado por f(T).

Uma MST (= minimum spanning tree) de um grafo com função-peso f é uma árvore geradora T do grafo que minimiza f(T). Considere o seguinte

Problema da MST:  Dado um grafo G com função-peso f nas arestas, encontrar uma MST de G.

Uma instância do problema da MST tem solução se e somente se G é conexo. Por isso, vamos nos restringir desde já a grafos conexos.

Exemplo A.  Cada linha representa uma aresta do grafo. O peso de cada aresta é proporcional ao comprimento geométrico do segmento de reta que representa a aresta na figura.

vw)	4 5	4 7	5 7	0 7	1 5	0 4	2 3	1 7	0 2	1 2	1 3	2 7	6 2	3 6	6 0	6 4
f(vw)	35	37	28	16	32	38	17	19	26	36	29	34	40	52	58	93

O conjunto de arestas  0 7 7 1 7 5 5 4 0 2 2 3 2 6  define uma árvore geradora do grafo. O peso dessa árvore é 35 + 28 + 16 + 17 + 19 + 26 + 40 = 181. Nenhuma outra árvore geradora tem peso menor, embora isso não seja óbvio.

O algoritmo de Prim

O célebre algoritmo de Prim, descoberto por R. C. Prim em 1957, resolve o problema da MST de maneira eficiente. (E. W. Dijkstra também descobriu o algoritmo.)

Nossa primeira descrição do algoritmo de Prim será feita num nível de abstração bastante alto. O algoritmo é iterativo. Cada iteração começa com uma subárvore T de G. Na primeira iteração, T tem um único vértice e nenhuma aresta. Imagine que os vértices de T são pretos e todos os demais são brancos. Diremos que a franja de T é o conjunto de todas as arestas de G que têm uma ponta preta e outra branca. O processo iterativo pode então ser descrito assim:

No fim de cada iteração, a ponta de vw que era branca fica preta e portanto a franja se altera. Quando a franja ficar vazia, T é uma árvore geradora de peso mínimo, a menos que G não seja conexo.

O algoritmo tem caráter guloso, pois escolhe o aresta vw com base em considerações locais, sem qualquer preocupação com o objetivo global de obter uma árvore de peso mínimo.

O algoritmo está correto.  Suponha que G é conexo, pois do contrário a instância do problema não tem solução. Nesse caso, é claro que o algoritmo produz uma árvore geradora. Resta mostrar que essa árvore é ótima, ou seja, tem peso mínimo. Para isso, basta provar que, no início de cada iteração,

Eis um esboço da prova. Suponha que no início de uma certa iteração T é sub­grafo de uma MST M. Durante esta iteração, uma aresta vw será acrescentada a T. Se essa aresta já está em M então T + vw é sub­grafo de M, como queríamos provar.

Suponha agora que vw não está em M. A árvore M tem um único caminho, digamos C, de v a w. Algum aresta xy de C está na franja de T e portanto f(xy) ≥ f(vw). Observe que

M + vw − xy

é uma árvore geradora. O peso dessa nova árvore não é maior que o peso de M. Concluímos que a nova árvore geradora é tão ótima quanto M. Finalmente, observe que T + vw é subgrafo de M + vw − xy.  Assim, no início da próxima iteração, T é subgrafo de uma MST, como queríamos provar.

Implementação do algoritmo de Prim

Tal como descrito na seção anterior, o algoritmo de Prim é ineficiente, uma vez que recalcula a franja de T a cada iteração (mesmo que ela tenha mudado muito pouco em relação à iteração anterior). Para que o algoritmo seja mais rápido, é preciso inventar uma representação eficiente da franja. É o que faremos a seguir.

No início de cada iteração, temos um conjunto Q de vértices e um vetor chave que associa um número a cada vértice do grafo. (O complemento de Q é o conjunto de vértices da subárvore T que está em construção.) 

No início de cada iteração, a franja é o conjunto de todas as arestas que têm uma ponta no complemento Q de Q e outra em Q. Para cada vértice w de Q, o número chave[w] é o peso da aresta mais leve dentre todas as arestas da franja que têm ponta w. O processo iterativo pode ser descrito assim:

Para reescrever o algoritmo de maneira mais formal e detalhada, vamos supor que o grafo G é conexo e representado por um vetor Adj de listas de adjacência. O conjunto Q será organizado como uma fila-com-prioridades. A árvore T será representada por um vetor de pais como o da página Distâncias e busca em largura.

Algumas observações que ajudam a entender o código:

• O rotina Nova-Fila-com-Prioridades cria uma fila vazia com prioridades ditadas por chave.
• Depois do bloco de linhas 1 a 8, Q contém todos vértices de G.
• A rotina Extraia-Min retira da fila um vértice com chave mínima (em particular, q sai de Q).
• Na linha 13, Diminua-Chave (w, Q, f(qw)) faz chave[w] := f(qw) e o que mais for preciso para restaurar a estrutura da fila-com-prioridades Q.
• Na linha 15, o vetor pai é transformado em um conjunto B de arestas. Na linha 16, o algoritmo devolve a subárvore (V, B).
• Para cada w, o valor de pai[w] é, em geral, alterado várias vezes ao longo da execução do algoritmo.

Desempenho.  O consumo de tempo do algoritmo Prim depende da implementação da fila-com-prioridades Q. Uma análise análoga à que fizemos no caso do algoritmo Dijkstra mostra que

• com uma implementação simples da fila, o algoritmo consome Ω(n² + m), sendo portanto quadrático no caso de instâncias esparsas e linear no caso de instâncias densas;
• com uma implementação da fila em um min-heap, o algoritmo consome Ο((n + m) lg n) unidades de tempo, sendo portanto linearítmico, quer o grafo seja esparso quer seja denso.

Note que o algoritmo Prim é assintoticamente mais rápido com a fila simples que com a fila sofisticada se nos restingirmos a grafos densos. (No caso da fila simples, nem é necessário construir a fila explícitamente: basta examinar todos os vértices de Q em cada iteração.)