Algoritmos para Grafos, via Sedgewick | Índice remissivo
Nosso problema nesta página é o mesmo da página anterior: encontrar uma MST (árvore geradora mínima) de um grafo G com custos nas arestas.
(Esta página é um resumo da seção 20.4 (Kruskal's Algorithm), p.246-252, do livro de Sedgewick.)
O algoritmo de Kruskal (publicado em 1956) se apoia nas condições otimalidade de MSTs para encontrar uma MST de um grafo.
Os seguintes conceitos serão usados para descrever o algoritmo de Kruskal. Todos são relativos a um grafo G:
Podemos agora descrever o algoritmo de Kruskal. Cada iteração começa com uma floresta geradora F do grafo. (No início da primeira iteração, cada componente de F tem apenas um vértice.) Cada iteração consiste no seguinte:
Se G for conexo, o algoritmo produz uma MST de G. Caso contrário, o algoritmo produz uma MST em cada componente de G.
Como decidir se uma aresta v-w é externa a uma floresta geradora? Basta fazer o seguinte: (1) em cada componente da floresta geradora, eleja um dos vértices para ser o representante do componente; (2) mantenha um vetor id[0..V-1] de representantes, sendo
id[v]
o representante do componente que contém o vértice v; (3) agora, v-w é externa se e somente se id[v] é diferente de id[w].
Nossa primeira implementação das ideias acima é simples mas ineficiente. Ela imprime uma lista das arestas de uma MST de um grafo G com custos nas arestas. O grafo é representado por sua matriz de adjacência. A função supõe que o custo de cada aresta é estritamente menor que maxCOST.
#define maxCOST 1000000.0void bruteforceKruskal (Graph G) { Vertex id[maxV], v, w; for (v = 0; v < G->V; v++) id[v] = v; while (1) { double mincost = maxCOST; Vertex v0, w0; for (v = 0; v < G->V; v++) for (w = 0; w < G->V; w++) if (G->adj[v][w] < mincost && id[v] != id[w]) mincost = G->adj[v0=v][w0=w]; if (mincost == maxCOST) return; printf("%d-%d\n", v0, w0); for (v = 0; v < G->V; v++) if (id[v] == id[w0]) id[v] = id[v0]; } }
Exemplo: Considere o grafo definido pela lista de arestas na coluna esquerda abaixo. A coluna do meio traz a mesma lista de arestas em ordem crescente de custos. O algoritmo de Kruskal examina as arestas nessa ordem. Na coluna da direita, as arestas rejeitadas pelo algoritmo estão riscadas. (Isto é uma cópia do figura 20.12, p.247, de Sedgewick.)
0-6 .51 0-1 .32 0-2 .29 4-3 .34 5-3 .18 7-4 .46 5-4 .40 0-5 .60 6-4 .51 7-0 .31 7-6 .25 7-1 .21 |
5-3 .18 7-1 .21 7-6 .25 0-2 .29 7-0 .31 0-1 .32 4-3 .34 5-4 .40 7-4 .46 0-6 .51 6-4 .51 0-5 .60 |
5-3 .18 7-1 .21 7-6 .25 0-2 .29 7-0 .31 |
Graph bruteK (Graph G) {
Graph T = GRAPHinit(G->V);
while (1) {
double mincost = maxCOST; link p;
Vertex v, v0, w0;
for (v = 0; v < G->V; v++)
for (p = G->adj[v]; p != NULL; p = p->next)
if (p->cost < mincost && !GRAPHpath(T, v, p->w)) {
mincost = p->cost;
v0 = v;
w0 = p->w;
}
if (mincost == maxCOST) return T;
GRAPHinsertE(T, v0, w0, mincost);
}
}
vértices 0 1 2 3 4 5
coordenadas (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 Kruskal a esse grafo. Exiba uma figura do grafo e da floresta no início de cada iteração.
Essa implementação começa por colocar todas as arestas do grafo em ordem crescente de custo. Preliminarmente, a função GRAPHedges armazena as arestas do grafo num vetor a[0..E-1]. Em seguida, uma função sort rearranja o vetor a[0..E-1] em ordem crescente de custos: a[0].cost ≤ a[1].cost ≤ …
#define maxE 10000/* A função abaixo é uma implementação do algoritmo de Kruskal. Ela recebe um grafo G com custos nas arestas e calcula uma MST em cada componente de G. A função armazena as arestas das MSTs no vetor mst[0..k-1] e devolve k. */
/* A função supõe que o grafo tem no máximo maxE arestas. Supõe também que o custo de cada aresta é estritamente menor que maxCOST. O código foi copiado, com ligeiras modificações, do programa 20.5, p.249, de Sedgewick. */
int GRAPHmstK (Graph G, Edge mst[]) { int i, k, E = G->A/2; Edge a[maxE]; GRAPHedges(a, G); sort(a, 0, E-1); UFinit(G->V); for (i = k = 0; i < E && k < G->V-1; i++) if (!UFfind(a[i].v, a[i].w)) { UFunion(a[i].v, a[i].w); mst[k++] = a[i]; } return k; }
No início de cada iteração, o conjunto de arestas mst[0..k-1] define uma floresta geradora de G. As as funções UFfind e UFunion têm o seguinte papel:
Para dar uma implementação eficiente às funções UFfind e UFunion, podemos usar uma versão melhorada do vetor de representantes sugerido acima. A estrutura que implementa essa versão melhorada é conhecida como union-find. (A estrutura union-find é discutida na seção 1.3, p.11-19, do volume 1 do livro de Sedgewick. Também aparece no programa 4.8, p.152, do mesmo livro.)
A estrutura union-find é uma floresta de nós. Os nós são os vértices de nosso grafo G, mas a floresta não é um subdigrafo de G. Cada componente da floresta é representado por uma union-find tree. Cada nó i da floresta tem um pai id[i]. Se i é a raiz de uma union-find tree então id[i] = i. Se i é raiz de uma union-find tree, então sz[i] é o número de nós na union-find tree.
/* (O código abaixo é uma versão adaptada do programa 4.8, p.152, do volume 1 do livro de Sedgewick). */
/* A função UFfind devolve 1 se os vértices v e w estiverem na mesma union-find tree (e portanto no mesmo componente da floresta mst[0..k-1]). */
/* A função UFunion faz a união das union-find trees que contêm os vértices v e w. */
static Vertex id[maxV]; static int sz[maxV]; void UFinit(int N) { Vertex i; for (i = 0; i < N; i++) { id[i] = i; sz[i] = 1; } } int UFfind(Vertex v, Vertex w) { return (find(v) == find(w)); } static Vertex find(Vertex x) { Vertex i = x; while (i != id[i]) i = id[i]; return i; } void UFunion(Vertex v, Vertex w) { Vertex i = find(v), j = find(w); if (i == j) return; if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; } else { id[j] = i; sz[i] += sz[j]; } }
(O código de GRAPHmstK pode parecer um pouco assustador porque depende de várias funções auxiliares. É um bom exercício escrever uma versão "compacta" da função GRAPHmstK que incorpore, tanto quanto razoável, o código das funções de manipulação da estrutura union-find. Essa versão compacta pode até corrigir uma pequena ineficiência do código acima, que calcula find(a[i].v) e find(a[i].w) duas vezes sem necessidade: um embutida em UFfind e outra em UFunion.)
Desempenho. Graças à maneira com duas union-find trees são fundidas em UFunion, a altura de cada union-find tree é limitada por log(V). Assim, UFfind e UFunion consomem tempo proporcional log(V).
Podemos supor que a função sort consome tempo proporcional a E log(E). O restante do código de GRAPHmstK também consome tempo proporcional a E log(E). Como log(E) ≤ 2log(V), podemos dizer que o consumo de GRAPHmstK é proporcional a
E log(V)
no pior caso.