PDF de programación - Estructuras de datos: Conjuntos disjuntos

Primer enfoque
Segundo enfoque

Estructuras de datos: Conjuntos disjuntos

Algoritmos

Facultad de Informática
Universidad de A Coruña

Algoritmos

Conjuntos disjuntos

Índice

Primer enfoque
Segundo enfoque

1 Primer enfoque

2 Segundo enfoque

Unión por alturas
Compresión de caminos

Algoritmos

Conjuntos disjuntos

Representación de conjuntos disjuntos

Primer enfoque
Segundo enfoque

Todos los elementos se numeran de 1 a n.
Cada subconjunto tomará su nombre de uno de sus elementos,
su representante, p. ej. el valor más pequeño.
Mantenemos en un vector el nombre del subconjunto disjunto
de cada elemento

1
C 1

2
2

3
3

4
2

5
1

6
3

7
2

8
3

9
3

10
2

Algoritmos

Conjuntos disjuntos

51271046389Operaciones válidas

Primer enfoque
Segundo enfoque

La representación inicial es una colección de n conjuntos, Ci.

Cada conjunto tiene un elemento diferente, Ci ∩ Cj = /0
Así, al principio se tiene Ci = {i}.

Hay dos operaciones válidas.

La búsqueda devuelve el nombre del conjunto
de un elemento dado.
La unión combina dos subconjuntos que contienen
a y b en un subconjunto nuevo, destruyéndose los originales.

Algoritmos

Conjuntos disjuntos

Pseudocódigo (i)

Primer enfoque
Segundo enfoque

tipo

Elemento = entero;
Conj = entero;
ConjDisj = vector [1..N] de entero

función Buscar1 (C, x) : Conj

devolver C[x]

fin función

La búsqueda es una simple consulta O(1).

El nombre del conjunto devuelto por búsqueda es arbitrario.
Todo lo que importa es que búsqueda(x)=búsqueda(y) si y sólo
si x e y están en el mismo conjunto.

Algoritmos

Conjuntos disjuntos

Pseudocódigo (ii)

Primer enfoque
Segundo enfoque

procedimiento Unir1 (C, a, b)

i := min (C[a], C[b]);
j := max (C[a], C[b]);
para k := 1 hasta N hacer

si C[k] = j entonces C[k] := i

fin para

fin procedimiento

La unión toma O(n). No importa, en lo que concierne a
corrección, qué conjunto retiene su nombre.
Una secuencia de n− 1 uniones (la máxima, ya que entonces
todo estaría en un conjunto) tomaría O(n2).
La combinación de m búsquedas y n− 1 uniones toma
O(m + n2).

Algoritmos

Conjuntos disjuntos

Índice

Primer enfoque
Segundo enfoque

Uni ón por alturas
Compresi ón de caminos

1 Primer enfoque

2 Segundo enfoque

Unión por alturas
Compresión de caminos

Algoritmos

Conjuntos disjuntos

Segundo enfoque

Primer enfoque
Segundo enfoque

Uni ón por alturas
Compresi ón de caminos

Se utiliza un árbol para caracterizar cada subconjunto.

La raíz nombra al subconjunto.
La representación de los árboles es fácil porque la única
información necesaria es un apuntador al padre.
Cada entrada p[i] en el vector contiene el padre del elemento i.

Si i es una raíz, entonces p[i]=i

1
C 1

2
2

3
3

4
2

5
1

6
3

7
4

8
3

9
3

10
4

Algoritmos

Conjuntos disjuntos

15247103689Pseudocódigo (i)

Primer enfoque
Segundo enfoque

Uni ón por alturas
Compresi ón de caminos

función Buscar2 (C, x) : Conj

r := x;
mientras C[r] <> r hacer

r := C[r]

fin mientras;
devolver r
fin función

Una búsqueda sobre el elemento x se efectúa
devolviendo la raíz del árbol que contiene x.
La búsqueda de un elemento x es proporcional a la profundidad
del nodo con x.

En el peor caso es O(n)

Algoritmos

Conjuntos disjuntos

Pseudocódigo (ii)

Primer enfoque
Segundo enfoque

Uni ón por alturas
Compresi ón de caminos

procedimiento Unir2 (C, raíz1, raíz2)

{ supone que raíz1 y raíz2 son raíces }

si raíz1 < raíz2 entonces C[raíz2] := raíz1
sino C[raíz1] := raíz2

fin procedimiento

La unión de dos conjuntos se efectúa combinando
ambos árboles: apuntamos la raíz de un árbol a la del otro.
La unión toma O(1).
La combinación de m búsquedas y n− 1 uniones toma O(m· n).

Algoritmos

Conjuntos disjuntos

Unión por alturas

Primer enfoque
Segundo enfoque

Uni ón por alturas
Compresi ón de caminos

Las uniones anteriores se efectuaban de modo arbitrario.
Una mejora sencilla es realizar las uniones haciendo del árbol
menos profundo un subárbol del árbol más profundo.

La altura se incrementa sólo cuando se unen dos árboles
de igual altura.

1
C 1

1
A 1

2
2

2
2

3
3

3
1

4
2

4

5
1

5

6
3

6

7
4

7

8
3

8

9
3

9

10
4

10

Algoritmos

Conjuntos disjuntos

15247103689Pseudocódigo

Primer enfoque
Segundo enfoque

Uni ón por alturas
Compresi ón de caminos

procedimiento Unir3 (C, A, raíz1, raíz2)

{ supone que raíz1 y raíz2 son raíces }

si A[raíz1] = A[raíz2] entonces

A[raíz1] := A[raíz1] + 1;
C[raíz2] := raíz1

sino si A[raíz1] > A[raíz2] entonces C[raíz2] := raíz1
sino C[raíz1] := raíz2

fin procedimiento

La profundidad de cualquier nodo nunca es mayor que log2(n).

Todo nodo está inicialmente a la profundidad 0.
Cuando su profundidad se incrementa como resultado de una
unión, se coloca en un árbol al menos el doble de grande.

Así, su profundidad se puede incrementar a lo más, log2(n) veces.

El tiempo de ejecución de una búsqueda es O(log(n)).
Combinando m búsquedas y n− 1 uniones, O(m· log(n) + n).

Algoritmos

Conjuntos disjuntos

Compresión de caminos

Primer enfoque
Segundo enfoque

Uni ón por alturas
Compresi ón de caminos

La compresión de caminos se ejecuta durante búsqueda.

Durante la búsqueda de un dato x, todo nodo en el camino de x
a la raíz cambia su padre por la raíz.
Es independiente del modo en que se efectúen las uniones.

función Buscar3 (C, x) : Conj

r := x;
mientras C[r] <> r hacer

r := C[r]

fin mientras;
i := x;
mientras i <> r hacer

j := C[i]; C[i]:= r; i := j

fin mientras;
devolver r
fin función

Algoritmos

Conjuntos disjuntos

Rangos

Primer enfoque
Segundo enfoque

Uni ón por alturas
Compresi ón de caminos

La compresión de caminos no es totalmente compatible con la
unión por alturas.

Al buscar, la altura de un árbol puede cambiar.

Las alturas almacenadas para cada árbol se convierten en
alturas estimadas (rangos).

Pero la unión por rangos es tan eficiente, en teoría, como la unión
por alturas.

Algoritmos

Conjuntos disjuntos

Ejemplo de compresión de caminos

Primer enfoque
Segundo enfoque

Uni ón por alturas
Compresi ón de caminos

Algoritmos

Conjuntos disjuntos

9820211610202116106411112Buscar3(20)986411112