22 Algoritmo de Prim

Algoritmo de Prim para encontrar uma MST de um grafo
ENTRADA: Grafo G=<V,E> e uma função w(u,v) que atribui valores a cada aresta (u,v) de E.
SAÍDA: Uma MST de G. Na verdade o que realmente importa é o conjunto de arestas.
Estratégia: Constrói uma árvore a partir de um vértice inicial qualquer, incorporando os outros vértices de V um a
um, junto com as arestas que o conectam à nova árvore sendo construída. Note que o que realmente importa são
as arestas que vão sendo usadas para conectar os vértices incorporados. No algoritmo abaixo as arestas serão
colocadas em E´e os vértices incorporados à MST sendo construída serão colocados em S.
ALGORITMO de Prim (overview):
1. Inicializa o conjunto S (saída) com um vértice qualquer de V, digamos r, de raiz. Inicializa o conjunto Q
com todos os vértices menos r ( Q <- V- {r} ). Note que sempre vamos ter a invariante F = V-Q.
Inicializa o conjunto E´com vazio.
2. Faz |V|-1 vezes:
1. Escolha uma aresta <u,v> tal que
e
, que tenha valor mínimo dentre todas as
outras. Isto é: considere o conjunto {<u,v>|
e
}, das arestas que conectam um
vértice de S com um vértice de Q. O algoritmo escolhe a aresta de menor valor deste conjunto.
2. Insira <u,v> em E´
3. Remova v de Q
4. Insira v em S
3.
Perguntas:
1. Suponha que existam duas implementações diferentes do algoritmo acima, e ambas sejam executadas
sobre o mesmo grafo, iniciando com o mesmo vértice r em S. É possível que as duas implementações
gerem como saída MSTs diferentes? Justifique.
2.
Por que o algoritmo funciona? Esta é a pergunta que não quer calar.
1. Primeiro convença que a escolha do vértice inicial r a ser colocado em S é irrelevante.
2. Depois verifique que, a cada início/fim de iteração, o grafo G´=<S,E´> é um subgrafo de G, e é uma árvore.
3. Considere a cada início de iteração o conjunto das arestas que cruzam entre S e Q, isto é, o conjunto
{<u,v>|
e
}. Convença-se que pelo menos uma das arestas deste conjunto deverá ser
incluída na MST sendo construída em <S,E´>. (Aliás, qualquer que seja a MST, construída por qualquer
algoritmo, deverá ter pelo menos uma aresta deste conjunto. Por que?). Isto significa que a restrição na
escolha das arestas à este conjunto a cada passo não é um problema.
4. O último ( e mais difícil ponto a ser provado ) é que a escolha da aresta de melhor valor, que é uma
escolha ótima local, também conduz a um resultado ótimo global, isto é, a uma MST. Este argumento
será visto em aula.
Definições adicionais relacionadas ao algoritmo de Prim:
1. Um corte (cut) em um grafo G=<V,T> é uma partição qualquer de V com duas classes de equivalências.
Representaremos o corte como um par <S, V-S> onde S é um subconjunto qualquer de V e V-S,
obviamente, o seu complemento. No algoritmo acima, a cada início/fim de iteração, <S, Q> define um
corte no grafo.
2. Uma aresta <u,v> cruza (crosses) um corte <S, V-S> se
lembre que o grafo é não dirigido).
e
(ou vice-versa,
Complexidade:
A parte relevante do algoritmo é o passo 2, que executa |V| vezes os passos 2.1 até 2.4. Dentre estes o passo
crítico é 2.1, que procura a aresta adequada. É fácil ver que a implementação deste algoritmo pode ser feita em
O(|V|*|E|), basta fazer uma pesquisa sequencial em todas as arestas. Se o grafo for denso (como no exemplo da
instalação elétrica que o grafo era completo, isto significará ~
passos.
Como fazer para reduzir a complexidade? Ordenar as arestas? Fazer pesquisa binária no conjunto ordenado das
arestas?
AQUI CABE UM MOMENTO DE REFLEXÃO SOBRE AS ALTERNATIVAS
A escolha de Prim foi pelo uso de uma "priority queue", implementada com uma "heap". (Aliás o escopo de uso
de heaps é bem mais amplo do simplesmente um componente do heapsort.) A priority queue usa uma heap com
operações para inserir elemento, extrair o maior/menor elemento (dependendo da utilização) e para consultar o
maior/menor elemento.As operações de inserção e remoção são O(log n) e a de consulta O(1). Uma outra
operação que pode ser também implementada na heap em O(log n) e adicionada à interface da priority queue é a
de alteração da chave de um elemento (alteração da prioridade), com consequente necessidade de rearranjá-lo
na heap. Esta operação é usada no algoritmo abaixo.
No algoritmo abaixo, pode-se supor que Q é implementado como uma heap dos vértices, e a ordem dos vértices
é de acordo com a função key[u]. A heap é organizada por valor mínimo e não máximo como no heapsort. O
acesso à heap e através das primitivas de priority queue usadas no algoritmo.
ALGORITMO de Prim (detalhe):
MST-PRIM (G = <V, E>, w) // w é a função de valor
1. para cada vértice v de V
1. key[v] <- infinito
2. anterior[v] <- NULL
2. para algum vértice r qualquer de V
1. key[r] <- 0
3. Q <- V // Cria a heap (build-heap) usando a key[v] para comparar os vértices
// Note que r está na raiz da heap
4. E' <- {} // Conjunto de arestas da MST inicia vazio
5. while Q != vazio (ou, faça |V| vezes)
1. u < extract-min // extrai vértice da raiz da heap e reorganiza heap
2. se (anterior[u] != NULL)
1. E'. insere (<anterior[u], u>)
3. para cada v em Adj(u)
1. if v está em Q e w(u,v) < key[v]
1. anterior [v] <- u
2. key [v] <- w(u,v) // Atenção: Isto também reorganiza a heap, mas de uma forma
que não tinhamos visto antes (* ver nota abaixo *)
6.
NOTA: O algoritmo acima exige uma heap que suporte alteração do valor da chave dos seus
elementos (alteração de prioridade) !!!! Infelizmente as heaps das bibliotecas das linguagens (e.g.
biblioteca STL do C++) não tem esta operação, que aliás pode ser feita em tempo
.
Complexidade do algoritmo:
1. Passo 3 é Theta (|V|)
2. O passo 4.1 é executado um total de |V| vezes cada vez com tempo log(n´) onde n´ é o número de vértices
remanescentes na heap. No total o custo é Theta (|V| log (|V|)).
3. O passo 4.2.1.1 também leva tempo log(n´), mas é executado uma vez para cada aresta (confira isto). O
total, portanto, é Theta (|E|*log(|V|).
Somando tudo, a complexidade é
número de arestas é no mínimo |V|-1, podemos simplificar como
. Como o grafo é conexo, e assim o
.
NOTA: A análise acima assume que as operações da heap tem custo
. Isto corresponde à heap
vista anteriormente com o heapsort. Existem implementações de heap ainda mais eficientes do que aquela
(binomial heap, Fibonacci heap). Naquele momento isto não fazia diferença, mas para este algoritmo faz. Não
vamos abordar isto aqui.
Fazer exemplo completo em aula executando o algoritmo