← Estructuras de datos desde cero · Lección 29/32
Union-Find: ¿están en el mismo grupo?
Cada quien apunta a su jefe
Union-Find (o conjuntos disjuntos) contesta dos cosas: unir dos grupos y encontrar a qué grupo pertenece alguien. Sirve para redes de amigos, para saber si dos puntos de un mapa están conectados y en el algoritmo de Kruskal.
Todo cabe en un arreglo padre: al principio cada elemento es su propio padre (un grupo de uno). Unir es colgar la raíz de un grupo de la raíz del otro. Encontrar es subir de padre en padre hasta la raíz, que es la que representa al grupo.
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
- El arreglo queda
[1, 2, 2, 4, 4, 5]: el 0 apunta al 1, el 1 al 2, el 3 al 4. Las raíces (2, 4 y 5) se apuntan a sí mismas, y son las resaltadas en el dibujo. - 0 y 2 tienen la misma raíz: mismo grupo. 0 y 3, no.
Toda la lección en una página
Cada quien apunta a su jefe
Union-Find (o conjuntos disjuntos) contesta dos cosas: unir dos grupos y encontrar a qué grupo pertenece alguien. Sirve para redes de amigos, para saber si dos puntos de un mapa están conectados y en el algoritmo de Kruskal.
Todo cabe en un arreglo padre: al principio cada elemento es su propio padre (un grupo de uno). Unir es colgar la raíz de un grupo de la raíz del otro. Encontrar es subir de padre en padre hasta la raíz, que es la que representa al grupo.
const padre = [0, 1, 2, 3, 4, 5];
function encontrar(x) {
while (padre[x] !== x) x = padre[x];
return x;
}
function unir(a, b) {
padre[encontrar(a)] = encontrar(b);
}
unir(0, 1);
unir(1, 2);
unir(3, 4);
console.log(padre);
console.log(encontrar(0) === encontrar(2));
console.log(encontrar(0) === encontrar(3));
- El arreglo queda
[1, 2, 2, 4, 4, 5]: el 0 apunta al 1, el 1 al 2, el 3 al 4. Las raíces (2, 4 y 5) se apuntan a sí mismas, y son las resaltadas en el dibujo. - 0 y 2 tienen la misma raíz: mismo grupo. 0 y 3, no.
Dos trucos: comprimir y colgar al chico
La versión sencilla puede formar cadenas largas (0→1→2→3→…) y entonces encontrar cuesta O(n). Se arregla con dos ideas:
- Compresión de caminos: al encontrar la raíz, cada nodo del camino se cuelga directo de ella. La siguiente vez es un solo salto.
- Unir por tamaño: el grupo chico se cuelga del grande, nunca al revés, para que el árbol no crezca en altura.
Con las dos, cada operación cuesta en la práctica casi O(1) (el costo real es la función inversa de Ackermann, que no pasa de 4 para cualquier tamaño que quepa en una computadora).
function crear(n) {
return { padre: Array.from({ length: n }, (_, i) => i), tam: new Array(n).fill(1) };
}
function encontrar(uf, x) {
if (uf.padre[x] !== x) uf.padre[x] = encontrar(uf, uf.padre[x]);
return uf.padre[x];
}
function unir(uf, a, b) {
let ra = encontrar(uf, a), rb = encontrar(uf, b);
if (ra === rb) return false;
if (uf.tam[ra] < uf.tam[rb]) [ra, rb] = [rb, ra];
uf.padre[rb] = ra;
uf.tam[ra] += uf.tam[rb];
return true;
}
const uf = crear(8);
unir(uf, 0, 1);
unir(uf, 2, 3);
unir(uf, 1, 3);
unir(uf, 4, 5);
console.log(uf.padre);
console.log(encontrar(uf, 3) === encontrar(uf, 0));
console.log(uf.padre);
console.log(unir(uf, 0, 2));
- Antes de buscar, el 3 todavía apunta al 2 (
[0, 0, 0, 2, …]). - Después de
encontrar(uf, 3), el 3 ya apunta directo al 0: eso es la compresión de caminos. unir(uf, 0, 2)dafalse: ya estaban en el mismo grupo y no hay nada que unir.
Contar grupos
Un uso clásico: tienes personas y una lista de amistades, y quieres saber cuántos grupos de amigos hay (contando a los amigos de tus amigos). Empiezas con n grupos y cada unir que de verdad junta dos grupos resta uno.
Es el mismo problema que contar islas en un mapa: cada casilla de tierra se une con su vecina de tierra, y al final cuentas cuántas raíces quedaron.
function crear(n) {
return { padre: Array.from({ length: n }, (_, i) => i), tam: new Array(n).fill(1) };
}
function encontrar(uf, x) {
if (uf.padre[x] !== x) uf.padre[x] = encontrar(uf, uf.padre[x]);
return uf.padre[x];
}
function unir(uf, a, b) {
let ra = encontrar(uf, a), rb = encontrar(uf, b);
if (ra === rb) return false;
if (uf.tam[ra] < uf.tam[rb]) [ra, rb] = [rb, ra];
uf.padre[rb] = ra;
uf.tam[ra] += uf.tam[rb];
return true;
}
const nombres = ["Ana", "Beto", "Caro", "Dani", "Eli", "Fer"];
const amistades = [[0, 1], [1, 2], [3, 4]];
const uf = crear(nombres.length);
let grupos = nombres.length;
for (const [a, b] of amistades) {
if (unir(uf, a, b)) grupos--;
}
console.log("grupos:", grupos);
const porRaiz = new Map();
nombres.forEach((nombre, i) => {
const r = encontrar(uf, i);
if (!porRaiz.has(r)) porRaiz.set(r, []);
porRaiz.get(r).push(nombre);
});
console.log([...porRaiz.values()]);
Tres grupos: Ana, Beto y Caro (Ana y Caro no son amigas directas, pero comparten a Beto); Dani y Eli; y Fer, sola.