Union-Find

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

Quick-find

O programa 1.1, de Sedgewick lê uma sequê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  M N/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 processar 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;
}

 


URL: www.ime.usp.br/~pf/mac0122-2002/
Atualizado em 2017-11-01
© Paulo Feofiloff
IME-USP