Fundamentos de Union-Find
1. Concepto y su introducción
Union-Find es una estructura de datos de tipo árbol, utilizada para manejar problemas de fusión y consulta de conjuntos disjuntos.
La idea de Union-Find es usar un array para representar todo el bosque (parent), el nodo raíz del árbol identifica de manera única un conjunto. Solo necesitamos encontrar la raíz del árbol de un elemento para determinar en qué conjunto se encuentra.
2. Descripción de aplicación
Union-Find se utiliza en algunos problemas conNelementos en problemas de aplicación de conjuntos. Generalmente, al inicio hacemos que cada elemento constituya un conjunto de un solo elemento, luego fusionamos los conjuntos a los que pertenecen los elementos del mismo grupo en cierto orden, y durante el proceso debemos buscar repetidamente en qué conjunto se encuentra un elemento. Este proceso parece no ser complicado, pero la cantidad de datos es enorme. Si se describiera con otras estructuras de datos, a menudo el espacio sería demasiado grande, la computadora no podría soportarlo, ni podría calcular el resultado en poco tiempo, por lo que solo se puede usar Union-Find para manejarlo.
3. Representación básica de datos de Union-Find
Como se muestra nuevamente en la figura anterior0、2、4、6、8Los siguientes son todos0este conjunto, que indica0、2、4、6、8que estos cinco elementos están conectados,1、3、5、7、9Los siguientes son todos1este conjunto, que indica0，1、3、5、7、9que estos cinco elementos están conectados.
Construye una clase UnionFind: inicializa, cada id[i] apunta a sí mismo, sin elementos fusionados:
public UnionFind1(int n) {
count = n;
id = new int[n];
// Inicializar, cada id[i] apunta a sí mismo, sin elementos fusionados
for (int i = 0; i < n; i++)
id[i] = i;
}
...
Código de ejemplo en Java
Descargar paquete de código fuente:Download
Código del archivo UnionFind.java:
public class UnionFind{
private int[] id;
// Número de datos
private int count;
public UnionFind1(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++)
id[i] = i;
}
}