Nosso problema neste artigo é o mesmo do anterior: encontrar uma MST (árvore geradora mínima) de um grafo G com custos nas arestas.
O algoritmo
O algoritmo de Prim (publicado em 1961) se apoia nas condições de otimalidade de MSTs para encontrar uma MST de um grafo G com custos nas arestas.
Para descrever o algoritmo, convém recorrer ao conceito de franja. A franja (= fringe) de uma subárvore não-geradora T de G é o conjunto de todas as arestas de G que têm uma ponta em T e outra ponta fora. Se denotarmos por X o conjunto dos vértices de T e por Y o conjunto dos vértices fora de X, podemos dizer que a franja é o conjunto das arestas que pertencem ao corte (X,Y).
No início de cada iteração do algoritmo de Prim temos uma árvore T. (No início da primeira iteração, T consiste em um único vértice.) Cada iteração consiste no seguinte:
1. se a franja de T não é vazia
1.1 então seja e uma aresta de custo mínimo na franja
1.2 comece nova iteração com T+e no papel de T
2. senão pare
Se G for conexo, o algoritmo produz uma MST de G. Caso contrário, o algoritmo produz uma MST de uma das componentes de G.
Implementação grosseira do algoritmo
Nossa primeira implementação do algoritmo de Prim é simples e óbvia mas ineficiente. A função abaixo recebe um grafo G com custos nas arestas e calcula uma MST da componente de G que contém o vértice 0. A MST é tratada como uma arborescência com raiz 0 e armazenada no vetor de pais pai.
A função supõe que o grafo é representado por sua matriz de adjacência e o custo de cada aresta é estritamente menor que maxCST.
Implementações eficientes
Toda implementação eficiente do algoritmo de Prim depende do conceito de custo de um vértice em relação a uma árvore. Dada uma árvore não-geradora do grafo, o custo de um vértice w que está fora da árvore é o custo de uma aresta mínima dentre as que incidem em w e estão na franja da árvore. Em outras palavras, o custo de w é o custo de uma aresta mínima dentre as que têm uma ponta na árvore e outra em w. Se nenhuma aresta da franja incide em w, o custo de w é maxCST (que é maior que o custo de qualquer aresta e portanto tem o sabor de ∞).
Nas implementações que examinaremos abaixo, os custos dos vértices e as arestas que justificam esses custos são representados pelos vetores
cst e fr.
O custo do vértice w em relação à árvore é cst[w]. Para cada vértice w fora da árvore, o vértice fr[w] está na árvore e a aresta que liga w a fr[w] tem custo cst[w]. Cada iteração do algoritmo de Prim escolhe um vértice w fora da árvore e adota fr[w] como valor de pai[w].
As implementações que examinaremos abaixo têm uma peculiaridade: no início da primeira iteração, a árvore (representada pelo vetor pai) está vazia. Durante a primeira iteração a árvore adquire seu primeiro vértice e a partir da segunda iteração a implementação passa a se comportar como o algoritmo descrito acima.
Implementação eficiente para grafos densos
A implementação abaixo é ótima para grafos densos. É apropriado, portanto, representar o grafo por uma matriz de adjacência:
/* Recebe grafo G com custos nas arestas e calcula uma MST da componente de G que contém o vértice 0. A função armazena a MST no vetor pai, tratando-a como uma arborescência com raiz 0. */
/* O grafo G é representado por sua matriz de adjacência. A função supõe que e.cst < maxCST para cada aresta e. Supõe também que o grafo tem no máximo maxV vértices. */
O fragmento de código
Desempenho: No pior caso, o consumo tempo da função primDenso é proporcional a V^2.
Portanto, a função primDenso é linear para grafos densos (pois o tamanho de tais grafos é proporcional a V^2).
Implementação eficiente para grafos esparsos
Esta seção discute uma implementação mais sofisticada do algoritmo de Prim. Ela usa uma fila de prioridades (= priority queue) para escolher, eficientemente, a próxima aresta a ser acrescentada à árvore.
A função primEsparso usa uma fila com prioridades. A fila é manipulada pelas seguintes funções:
PQinit(): inicializa uma fila de vértices em que cada vértice v tem prioridade cst[v].
PQempty(): devolve 1 se a fila estiver vazia e 0 em caso contrário.
PQinsert(v): insere o vértice v na fila.
PQdelmin(): retira da fila um vértice de prioridade mínima.
PQdec(w): reorganiza a fila depois que o valor de cst[w] foi decrementado.
A implementação clássica da fila de prioridades usa uma estrutura de heap. O heap é armazenado num vetor pq[1..N] (a posição 0 do vetor não é usada). A prioridade de um vértice pq[k] no heap é cst[pq[k]]. Propriedade fundamental do heap:
cst[pq[k/2]] ≤ cst[pq[k]]
para k=2,..,N. Portanto, o vértice pq[1] minimiza cst.
(O código de primEsparso pode parecer um pouco assustador porque depende de um grande número de funções auxiliares. Pode ser um bom exercício escrever uma versão "compacta" da função primEsparso, que incorpore, tanto quanto razoável, o código das funções de manipulação da fila de prioridades.)
Desempenho: Eis uma estimativa do consumo de tempo no pior caso de cada uma das funções de manipulação da fila de prioridades quando aplicada a um grafo com V vértices:
PQinit: constante, ou seja, não depende de V;
PQempty: constante, ou seja, não depende de V;
PQinsert: proporcional a lg(V);
PQdelmin: proporcional a lg(V);
PQdec: proporcional a lg(V).
Assim, o consumo de tempo da função primEsparso é proporcional a V lg(V) + E lg(V) no pior caso. Para grafos conexos, essa expressão se reduz a
E lg(V).
Portanto, a função primEsparso é um pouco pior que linear. Mesmo assim, esse desempenho é melhor que o da função primDenso quando os grafos são esparsos.
Outra implementação para grafos esparsos
O código abaixo é uma variante da função primEsparso. Nessa variante, os vértices são todos colocados na fila de prioridades antes do início do processo iterativo. O vetor pai usurpa o papel de fr e fr é dispensado. Com isso, o valor de cada elemento de pai pode ser alterados várias vezes ao longo do processo iterativo (ao contrário do que acontece em primEsparso).
O código dessa variante é mais curto que o de primEsparso (embora não seja mais eficiente). Por isso, há quem considere essa variante mais atraente.
Exercícios para Fixação
1. Qual a diferença entre grafos esparsos e grafos densos?
2. Esta afirmação: "A implementação abaixo é ótima para grafos densos. É apropriado, portanto, representar o grafo por uma matriz de adjacência." está correta? Porque?
3. Qual a vantagem de se saber se o grafo é esparso ou denso quando precisamos saber sua árvore geradora mínima?
4. Porque usar uma fila de prioridade ao invés de utilizar uma fila comum?
Fonte: IME
O algoritmo
O algoritmo de Prim (publicado em 1961) se apoia nas condições de otimalidade de MSTs para encontrar uma MST de um grafo G com custos nas arestas.
Para descrever o algoritmo, convém recorrer ao conceito de franja. A franja (= fringe) de uma subárvore não-geradora T de G é o conjunto de todas as arestas de G que têm uma ponta em T e outra ponta fora. Se denotarmos por X o conjunto dos vértices de T e por Y o conjunto dos vértices fora de X, podemos dizer que a franja é o conjunto das arestas que pertencem ao corte (X,Y).
No início de cada iteração do algoritmo de Prim temos uma árvore T. (No início da primeira iteração, T consiste em um único vértice.) Cada iteração consiste no seguinte:
1. se a franja de T não é vazia
1.1 então seja e uma aresta de custo mínimo na franja
1.2 comece nova iteração com T+e no papel de T
2. senão pare
Se G for conexo, o algoritmo produz uma MST de G. Caso contrário, o algoritmo produz uma MST de uma das componentes de G.
Implementação grosseira do algoritmo
Nossa primeira implementação do algoritmo de Prim é simples e óbvia mas ineficiente. A função abaixo recebe um grafo G com custos nas arestas e calcula uma MST da componente de G que contém o vértice 0. A MST é tratada como uma arborescência com raiz 0 e armazenada no vetor de pais pai.
A função supõe que o grafo é representado por sua matriz de adjacência e o custo de cada aresta é estritamente menor que maxCST.
void primForcaBruta() {
int v, w;
for (w = 0; w < n; w++) pai[w] = -1;
pai[0] = 0;
while (1) {
double mincst = maxCST;
int v0, w0;
for (w = 0; w < n; w++)
if (pai[w] == -1)
for (v = 0; v < n; v++)
if (pai[v] != -1 && mincst > G[v][w])
mincst = G[v0=v][w0=w];
if (mincst == maxCST) break;
/* A */
pai[w0] = v0;
}
}
No ponto A, v0-w0 é uma aresta de custo mínimo dentre as que estão na franja da árvore. O custo da aresta v0-w0 é mincst.Implementações eficientes
Toda implementação eficiente do algoritmo de Prim depende do conceito de custo de um vértice em relação a uma árvore. Dada uma árvore não-geradora do grafo, o custo de um vértice w que está fora da árvore é o custo de uma aresta mínima dentre as que incidem em w e estão na franja da árvore. Em outras palavras, o custo de w é o custo de uma aresta mínima dentre as que têm uma ponta na árvore e outra em w. Se nenhuma aresta da franja incide em w, o custo de w é maxCST (que é maior que o custo de qualquer aresta e portanto tem o sabor de ∞).
Nas implementações que examinaremos abaixo, os custos dos vértices e as arestas que justificam esses custos são representados pelos vetores
cst e fr.
O custo do vértice w em relação à árvore é cst[w]. Para cada vértice w fora da árvore, o vértice fr[w] está na árvore e a aresta que liga w a fr[w] tem custo cst[w]. Cada iteração do algoritmo de Prim escolhe um vértice w fora da árvore e adota fr[w] como valor de pai[w].
As implementações que examinaremos abaixo têm uma peculiaridade: no início da primeira iteração, a árvore (representada pelo vetor pai) está vazia. Durante a primeira iteração a árvore adquire seu primeiro vértice e a partir da segunda iteração a implementação passa a se comportar como o algoritmo descrito acima.
Implementação eficiente para grafos densos
A implementação abaixo é ótima para grafos densos. É apropriado, portanto, representar o grafo por uma matriz de adjacência:
/* Recebe grafo G com custos nas arestas e calcula uma MST da componente de G que contém o vértice 0. A função armazena a MST no vetor pai, tratando-a como uma arborescência com raiz 0. */
/* O grafo G é representado por sua matriz de adjacência. A função supõe que e.cst < maxCST para cada aresta e. Supõe também que o grafo tem no máximo maxV vértices. */
void primDenso() {
double cst[maxV];
int v0, w, fr[maxV];
for (w = 0; w < n; w++) { pai[w] = -1; cst[w] = maxCST; } v0 = 0; fr[v0] = v0; cst[v0] = 0.0; while (1) { double mincst = maxCST; for (w = 0; w < n; w++) if (pai[w] == -1 && mincst > cst[w])
mincst = cst[v0=w];
if (mincst == maxCST) break;
pai[v0] = fr[v0];
for (w = 0; w < n; w++) if (pai[w] == -1 && cst[w] > G[v0][w]) {
cst[w] = G[v0][w];
fr[w] = v0;
}
}
}
O fragmento de código
if (cst[w] > G[v0][w]) {
cst[w] = G[v0][w];
}
é característico do algoritmo de Prim. A operação que ele executa é conhecida como relaxação (da aresta v0-w). Essa operação aparece em toda implementação do algoritmo.Desempenho: No pior caso, o consumo tempo da função primDenso é proporcional a V^2.
Portanto, a função primDenso é linear para grafos densos (pois o tamanho de tais grafos é proporcional a V^2).
Implementação eficiente para grafos esparsos
Esta seção discute uma implementação mais sofisticada do algoritmo de Prim. Ela usa uma fila de prioridades (= priority queue) para escolher, eficientemente, a próxima aresta a ser acrescentada à árvore.
static double cst[maxV];
/* Recebe grafo G com custos nas arestas e calcula uma MST da componente de G que contém o vértice 0. A função armazena a MST no vetor pai, tratando-a como uma arborescência com raiz 0. */
/* O grafo G é representado por listas de adjacência. */
void primEsparso() {
int v0, w, fr[maxV], p;
PQinit();
for (w = 0; w < n; w++)
pai[w] = fr[w] = -1;
v0 = 0;
fr[v0] = v0;
cst[v0] = 0.0;
PQinsert(v0);
while (!PQempty()) {
v0 = PQdelmin();
pai[v0] = fr[v0];
for (p = 0; p < grau[v0]; p++) {
w = g[v0][p].w;
if (pai[w] == -1) {
if (fr[w] == -1) {
cst[w] = g[v0][p].cst;
PQinsert(w);
fr[w] = v0;
}
else if (cst[w] > g[v0][p].cst) {
cst[w] = g[v0][p].cst;
PQdec(w);
fr[w] = v0;
}
}
}
}
}
(Note a operação de relaxação if (cst[w] > g[v0][p].cst) { cst[w] = g[v0][p].cst; } característica do algoritmo de Prim.)A função primEsparso usa uma fila com prioridades. A fila é manipulada pelas seguintes funções:
PQinit(): inicializa uma fila de vértices em que cada vértice v tem prioridade cst[v].
PQempty(): devolve 1 se a fila estiver vazia e 0 em caso contrário.
PQinsert(v): insere o vértice v na fila.
PQdelmin(): retira da fila um vértice de prioridade mínima.
PQdec(w): reorganiza a fila depois que o valor de cst[w] foi decrementado.
A implementação clássica da fila de prioridades usa uma estrutura de heap. O heap é armazenado num vetor pq[1..N] (a posição 0 do vetor não é usada). A prioridade de um vértice pq[k] no heap é cst[pq[k]]. Propriedade fundamental do heap:
cst[pq[k/2]] ≤ cst[pq[k]]
para k=2,..,N. Portanto, o vértice pq[1] minimiza cst.
/*Supõe-se que N ≤ maxV. */
/* O vetor qp é o "inverso" de pq: para cada vértice v, qp[v] é o único índice tal que pq[qp[v]] == v. É claro que qp[pq[i]] == i para todo i. */
static Vertex pq[maxV+1];
static int N;
static int qp[maxV];
void PQinit(void) {
N = 0;
}
int PQempty(void) {
return N == 0;
}
void PQinsert(Vertex v) {
qp[v] = ++N;
pq[N] = v;
fixUp(N);
}
Vertex PQdelmin(void) {
exch(1, N);
--N;
fixDown(1);
return pq[N+1];
}
void PQdec(Vertex w) {
fixUp(qp[w]);
}
static void exch(int i, int j) {
Vertex t;
t = pq[i]; pq[i] = pq[j]; pq[j] = t;
qp[pq[i]] = i;
qp[pq[j]] = j;
}
static void fixUp(int k) {
while (k > 1 && cst[pq[k/2]] > cst[pq[k]]) {
exch(k/2, k);
k = k/2;
}
static void fixDown(int k) {
int j;
while (2*k <= N) {
j = 2*k;
if (j < N && cst[pq[j]] > cst[pq[j+1]]) j++;
if (cst[pq[k]] <= cst[pq[j]]) break;
exch(k, j);
k = j;
}
}
(O código de primEsparso pode parecer um pouco assustador porque depende de um grande número de funções auxiliares. Pode ser um bom exercício escrever uma versão "compacta" da função primEsparso, que incorpore, tanto quanto razoável, o código das funções de manipulação da fila de prioridades.)
Desempenho: Eis uma estimativa do consumo de tempo no pior caso de cada uma das funções de manipulação da fila de prioridades quando aplicada a um grafo com V vértices:
PQinit: constante, ou seja, não depende de V;
PQempty: constante, ou seja, não depende de V;
PQinsert: proporcional a lg(V);
PQdelmin: proporcional a lg(V);
PQdec: proporcional a lg(V).
Assim, o consumo de tempo da função primEsparso é proporcional a V lg(V) + E lg(V) no pior caso. Para grafos conexos, essa expressão se reduz a
E lg(V).
Portanto, a função primEsparso é um pouco pior que linear. Mesmo assim, esse desempenho é melhor que o da função primDenso quando os grafos são esparsos.
Outra implementação para grafos esparsos
O código abaixo é uma variante da função primEsparso. Nessa variante, os vértices são todos colocados na fila de prioridades antes do início do processo iterativo. O vetor pai usurpa o papel de fr e fr é dispensado. Com isso, o valor de cada elemento de pai pode ser alterados várias vezes ao longo do processo iterativo (ao contrário do que acontece em primEsparso).
O código dessa variante é mais curto que o de primEsparso (embora não seja mais eficiente). Por isso, há quem considere essa variante mais atraente.
static double cst[maxV];
void primSimples() {
int v0, w, p;
PQinit();
for (w = 0; w < n; w++) {
pai[w] = -1;
cst[w] = maxCST;
PQinsert(w);
}
v0 = 0;
pai[v0] = v0;
cst[v0] = 0.0;
PQdec(v0);
while (!PQempty()) {
v0 = PQdelmin();
if (cst[v0] == maxCST) break;
for (p = 0; p < grau[v0]; p++) {
w = g[v0][p].w;
if (cst[w] > g[v0][p].cst) {
cst[w] = g[v0][p].cst;
PQdec(w);
pai[w] = v0;
}
}
}
}Exercícios para Fixação
1. Qual a diferença entre grafos esparsos e grafos densos?
2. Esta afirmação: "A implementação abaixo é ótima para grafos densos. É apropriado, portanto, representar o grafo por uma matriz de adjacência." está correta? Porque?
3. Qual a vantagem de se saber se o grafo é esparso ou denso quando precisamos saber sua árvore geradora mínima?
4. Porque usar uma fila de prioridade ao invés de utilizar uma fila comum?
Fonte: IME
