Algoritmos para Grafos | Índice
Este capítulo discute o algoritmo de Boruvka para o problema da MST. Apesar de ter sido publicado em 1926, o algoritmo é menos conhecido que os de Prim e Kruskal. O problema pode ser formulado assim:
Problema: Encontrar uma MST (árvore geradora de custo mínimo) de um grafo não-dirigido com custos nas arestas.
Os custos das arestas são números inteiros arbitrários (positivos e negativos). Alguns conceitos básicos sobre esse problema podem ser vistos no capítulo geral sobre árvores geradoras de custo mínimo.
O problema tem solução se e somente se o grafo é conexo. Assim, vamos tratar apenas de grafos não-dirigidos conexos, embora essa restrição não seja muito séria (veja exercício abaixo).
Para descrever o algoritmo, é importante lembrar que cada aresta de um grafo não-dirigido consiste em dois arcos antiparalelos. Vamos supor (em consonância com nossa estrutura de dados) que o custo de cada um desses dois arcos é igual ao custo da aresta. O algoritmo manipula os dois arcos de cada aresta independentemente. Assim, durante a execução do algoritmo, pode ocorrer que apenas um dos arcos de algumas arestas é escolhido para fazer parte da árvore geradora. No fim, entretanto, ambos os arcos de cada aresta da árvore estarão presentes.
Será necessário fazer uma adaptação previsível do conceito de franja. Diremos que a franja (= fringe) de uma árvore T de nosso grafo G é o conjunto de todos os arcos que saem de T, ou seja, a franja é o leque de saída do conjunto de vértices de T. Diremos, ainda, que um arco é externo a uma floresta geradora F de G se tiver pontas em duas árvores diferentes de F. É claro que cada arco externo a F está na franja de exatamente uma das árvores de F.
Cada iteração do algoritmo de Boruvka começa com uma floresta geradora F de G. No início da primeira iteração, cada árvore de F tem apenas um vértice. O processo iterativo consiste no seguinte:
Diremos que B é um conjunto de Boruvka. Cada árvore da floresta F contribui um arco de sua franja para esse conjunto. (É interessante o sabor de processamento paralelo desse algoritmo: cada componente de F escolhe o arco mais barato de sua franja, e todas as componentes podem fazer isso ao mesmo tempo e independentemente.)
Se o grafo F + B não tiver circuitos, então B' será igual a B. Caso contrário, será preciso descartar alguns arcos de B para obter B'. O cálculo de B' e B'' e a substituição de F por F + B' + B'' são realizados, simultaneamente, pelo seguinte processo iterativo: examine os arcos de B um a um; se um arco for externo à floresta corrente, acrescente-o à floresta juntamente com seu arco antiparalelo; senão, descarte-o.
Exemplo A. A tabela abaixo define um grafo não-dirigido conexo e os custos de suas arestas.
0-1 0-2 1-2 1-3
1 1 1 2
No início da primeira iteração do algoritmo de Boruvka, cada árvore da floresta F tem um único vértice. Suponha que o algoritmo escolhe os seguintes arcos:
árvore 0 1 2 3
franja 0-2 1-0 2-1 3-1
O grafo não-dirigido F + B contém o ciclo 0-2-1-0 . Para obter B', basta eliminar qualquer um dos três arcos do ciclo. Se eliminarmos o arco 2-1, a próxima iteração começará com a floresta que tem arestas 0-2, 0-1 e 1-3. (Se o algoritmo tivesse escolhido o conjunto de arcos abaixo, o grafo não-dirigido F +B não teria ciclos de comprimento ≥ 3, e nesse caso B' seria igual a B.)
árvore 0 1 2 3
franja 0-2 1-0 2-0 3-1
0-1 0-2 0-3 1-2 2-3 3-1
3 5 5 7 7 7
0-4 0-1 5-4 4-2 0-3 1-6 6-2 2-7 7-3 3-5 5-1
0 3 4 5 5 7 0 7 0 7 0
0-1 0-2 0-3 1-2 2-3 3-1
2 5 2 2 2 7
Nossa primeira implementação do algoritmo de Boruvka é simples mas um tanto ineficiente. Como no algoritmo de Kruskal, um dos vértices de cada árvore da floresta será o chefe da árvore. Denotaremos por chefe[v] o chefe da árvore que contém o vértice v. Se x é o chefe de um árvore então chefe[x] é igual a x.
O código abaixo supõe que o grafo é representado por sua listas de adjacência e que o custo de cada aresta é menor que INFINITY.
![[!]](../gif/attention-black-on-yellow.jpg){kind=small}
Cada iteração começa com uma floresta F e tem duas fases.
Na primeira fase, o algoritmo
escolhe um conjunto de Boruvka B
e armazena os arcos desse conjunto num vetor bvka[].
Na segunda,
o algoritmo incorpora uma parte B' de B,
juntamente com os arcos antiparalelos aos de B',
à floresta F.
typedef struct {
vertex v, w;
int c;
} arc;
#define UGraph Graph
void naiveBoruvka( UGraph G) {
arc bvka[1000], chefe[1000], ar;
vertex u, v, x, y; link a;
int AA;
for (v = 0; v < G->V; ++v) chefe[v] = v;
while (true) {
for (u = 0; u < G->V; ++u)
bvka[u] = ARC( u, u, INFINITY);
AA = 0;
for (v = 0; v < G->V; ++v) {
for (a = G->adj[v]; a != NULL; a = a->next) {
x = chefe[v]; y = chefe[a->w];
if (x != y) {
if (a->c < bvka[x].c)
bvka[x] = ARC( v, a->w, a->c);
AA++;
}
}
}
if (AA == 0) break;
for (u = 0; u < G->V; ++u) {
ar = bvka[u];
x = chefe[ar.v]; y = chefe[ar.w];
if (x != y) {
printf( "%d-%d ", ar.v, ar.w);
for (v = 0; v < G->V; ++v)
if (chefe[v] == x) chefe[v] = y;
}
}
}
}
arc ARC( vertex v, vertex w, int c) {
arc ar;
ar.v = v, ar.w = w;
ar.c = c;
return ar;
}
Cada iteração tem duas fases: a primeira constói o conjunto de Boruvka e a segunda incorpora parte desse conjunto à floresta F. No fim da primeira fase, AA é o número de arcos externos e, para cada vértice x que é o chefe de uma árvore da floresta,
o arco bvka[x] é mínimo dentre os que estão na franja da árvore chefiada por x.
Exemplo B. Aplique a função naiveBoruvka() ao grafo não-dirigido definido pela lista de arestas abaixo.
0-6 0-1 0-2 4-3 5-3 7-4 5-4 0-5 6-4 7-0 7-6 7-1
51 32 29 34 18 46 40 60 51 31 25 21
Veja o estado do vetor chefe[] no início de sucessivas iterações:
0 1 2 3 4 5 6 7
2 7 2 5 5 5 7 7
7 7 7 7 7 7 7 7
Eis as arestas impressas no fim de sucessivas iterações (temos apenas duas iterações nesse exemplo).
0-2 1-7 3-5 4-3 6-7
0-7 4-7
Uma implementação eficiente do algoritmo de Boruvka usa as ideias da função naiveBoruvka() combinadas com uma estrutura union-find. Nas primeiras linhas do código abaixo, o conjunto de arcos do grafo não-dirigido G é armazenado, em ordem abitrária, num vetor external[0..A-1]. Cada arco é representado por uma struct arc que contêm as duas pontas do arco e o seu custo.
#define edge arc #define UGraph Graph
/* A função UGRAPHmstB() recebe um grafo não-dirigido conexo G com custos nas arestas e calcula uma MST de G. A função armazena as arestas das MSTs no vetor mst[0..k-1] e devolve k (que deve ser igual a G->V-1). */
/* A função supõe que INFINITY é maior que o custo de qualquer aresta. Supões também que G tem no máximo 1000 vértices e no máximo 500000 arestas. O código é uma versão corrigida do programa 20.6 de Sedgewick. */
int UGRAPHmstB( UGraph G, edge mst[]) { arc bvka[1000], external[2*500000], ar; vertex x, y, u, v, w; int A = G->A, E = G->A/2, k = 0; GRAPHarcs( G, external); UFinit( G->V); while (true) { int h, AA = 0; for (u = 0; u < G->V; ++u) bvka[u] = ARC( u, u, INFINITY); for (h = 0; h < A; ++h) { ar = external[h]; x = UFfind( ar.v); y = UFfind( ar.w); if (x != y) { if (ar.c < bvka[x].c) bvka[x] = ar; external[AA++] = ar; } } if (AA == 0) break; A = AA; for (u = 0; u < G->V; ++u) { ar = bvka[u]; if (ar.v == ar.w) continue; x = UFfind( ar.v); y = UFfind( ar.w); if (x != y) { UFunion( x, y); mst[k++] = ar; } } } return k; }
/* A função GRAPHarcs() armazena os arcos do grafo G no vetor external[0..A-1]. */
void GRAPHarcs( UGraph G, arc external[]) { int i = 0; link a; for (v = 0; v < G->V; ++v) for (a = G->adj[v]; a != NULL; a = a->next) external[i++] = ARC( v, a->w, a->c); }
Cada iteração começa com a floresta geradora mst[0..k-1] e tem duas fases: a primeira constói o conjunto de Boruvka e a segunda incorpora parte desse conjunto à floresta. No início de cada iteração, external[0..A-1] contém todos os arcos externos em relação à floresta geradora corrente (e possivelmente alguns arcos não externos). No fim da primeira fase da iteração, o vetor bvka[0..V-1] contém um conjunto de Boruvka representado da seguinte maneira: para cada vértice x que é chefe de uma árvore, bvka[x] é um arco mínimo da franja da árvore. (Além disso, o conjunto external[0..A-1] é comprimido pela eliminação dos arcos que não são mais externos.)
As funções UFfind() e UFunion() têm o seguinte papel:
Para dar uma implementação eficiente às funções UFfind()
e UFunion(),
o vetor chefe[] que usamos na seção anterior
é definido de maneira mais flexível.
Um vetor chf[0..V-1] representa essa versão mais flexível.
A flexibilização consiste no seguinte:
para cada vértice v,
o vértice chf[v]
pode não ser o chefe de v,
desde que seja possível chegar ao chefe iterando chf[],
ou seja,
fazendo
chf[chf[v]],
chf[chf[chf[v]]],
etc.
Com essa flexibilização,
chf[v] passa a ser uma espécie de
superior imediato
ou
pai
de v.
É claro que chf[v] deve ser igual a v
se e somente se v é um chefe.
A implementação do union-find abaixo é mais eficiente, no sentido amortizado, que a que usamos na implementação do algoritmo de Kruskal: além do truque union-by-rank, ela usa o truque path compression. O tamanho das árvores é mantido em um vetor sz[]: se x é um chefe então sz[x] é o número de vértices chefiados por x.
/* A função UFfind() devolve o chefe de v (ou seja, o chefe da árvore que contém v na floresta geradora corrente). A função UFunion() recebe dois chefes distintos x e y e faz a união das correspondentes árvores. */
static vertex chf[1000]; static int sz[1000]; void UFinit( int V) { for (vertex v = 0; v < V; ++v) { chf[v] = v; sz[v] = 1; } }
vertex UFfind( vertex v) { for (vertex x = v; x != chf[x]; x = chf[x]) chf[x] = chf[chf[x]]; // path compression return x; }
void UFunion( vertex x, vertex y) { if (sz[x] < sz[y]) { chf[x] = y; sz[y] += sz[x]; } else { chf[y] = x; sz[x] += sz[y]; } }
(O código de UGRAPHmstB() pode parecer um pouco assustador porque depende de várias funções auxiliares. É um bom exercício escrever uma versão all-in-one da função UGRAPHmstB() que incorpore, tanto quanto razoável, o código das funções de manipulação da estrutura union-find.)
Desempenho. Graças ao path compression, o consumo amortizado de tempo de cada execução da função UFfind() é proporcional a log* E, sendo E o número de arestas do grafo.
Cada iteração reduz o número de árvores da floresta F pelo menos à metade. Assim, o número de iterações não passa de log V. Com isso, o consumo de tempo da implementação UGRAPHmstB() do algoritmo de Boruvka é proporcional a
E log V log* E
no pior caso. Na prática, isto é essencialmente o mesmo que E log V. Mesmo essa estimativa é muito pessimista: na prática, o consumo de tempo é, em geral, proporcional a E.
0 1 2 3 4 5
(1,3)(2,1)(6,5)(3,4)(3,7)(5,3)
Suponha que as arestas do grafo são
1-0 3-5 5-2 3-4 5-1 0-3 0-4 4-2 2-3
e o custo de cada aresta v-w é igual ao comprimento do segmento de reta que liga os pontos v e w no plano. Aplique o algoritmo de Boruvka a esse grafo. Exiba uma figura do grafo e da floresta no início de cada iteração.
if (x != y)(na parte final do código da função UGRAPHmstB()) é realmente necessário? (Dica: Considere arestas de mesmo custo.)