Union-Find

Este é um resumo da seção 1.1 do livro de Sedgewick.

Quick-find

O programa 1.1, p.12, de Sedgewick lê uma seqüência de pares de inteiros, todos no intervalo [0..N-1]. Cada par (p,q) é interpretado como "ligue os objetos p e q". O programa imprime o par lido se e só se os objetos ainda não estão ligados (direta ou indiretamente).

#define N 10000 main(void) { int i, p, q, t, id[N]; for (i = 0; i < N; i++) id[i] = i; while (scanf("%d %d\n", &p, &q) == 2) { if (id[p] == id[q]) continue; t = id[p]; for (i = 0; i < N; i++) if (id[i] == t) id[i] = id[q]; printf(" %d %d\n", p, q); } }

Invariante: No começo de cada iteração, id[i] == id[j] se e só se i e j estão ligados (direta ou indiretamente).

Quick-union

Eis o programa 1.2 de Sedgewick:

while (scanf("%d %d\n", &p, &q) == 2) { for (i = p; i != id[i]; i = id[i]) ; for (j = q; j != id[j]; j = id[j]) ; if (i == j) continue; id[i] = j; printf(" %d %d\n", p, q); }

Tempo para processar M pares de N objetos: da ordem de  MN/2  no pior caso.

Weighted quick-union

Eis o programa 1.3 de Sedgewick:

int sz[N]; while (scanf("%d %d\n", &p, &q) == 2) { for (i = p; i != id[i]; i = id[i]) ; for (j = q; j != id[j]; j = id[j]) ; if (i == j) continue; if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; } else { id[j] = i; sz[i] += sz[j]; } printf(" %d %d\n", p, q); }

Invariante: no começo de cada iteração, para cada i tal que id[i] == i, a árvore cuja raiz é i tem exatamente sz[i] elementos.

Tempo para processar M pares de N objetos: não mais que M lg N .

Path compression

Para obter o programa 1.4 de Sedgewick basta trocar os "for" do programa anterior:

int sz[N]; while (scanf("%d %d\n", &p, &q) == 2) { for (i = p; i != id[i]; i = id[i]) id[i] = id[id[i]]; for (j = q; j != id[j]; j = id[j]) id[j] = id[id[j]]; if (i == j) continue; if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; } else { id[j] = i; sz[i] += sz[j]; } printf(" %d %d\n", p, q); }

Eis uma versão um pouco diferente do programa:

while (scanf("%d %d\n", &p, &q) == 2) { for (i = p; i != id[i]; i = id[i]) ; for (j = q; j != id[j]; j = id[j]) ; if (i == j) continue; if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; t = j; } else { id[j] = i; sz[i] += sz[j]; t = i; } for (i = p; i != id[i]; i = id[i]) id[i] = t; for (j = q; j != id[j]; j = id[j]) id[j] = t; printf(" %d %d\n", p, q); }

Quanto tempo o programa consome para rpocessar M pares de N objetos?  Demonstra-se (a prova é difícil!) que o consumo de tempo é proporcional a

M lg^*(N)

no pior caso.  A função  lg^*  é definida assim:

int lg_estrela (int N) {
   int i = 0, n = N;
   while (n > 1) {
      n = lg(n);
      i++;
   }
   return i;
}