Union-Find: Quick Find
Esta sección se basa en la estructura de Union-Find de la sección anterior para presentar las operaciones básicas: consulta, unión y comprobación de si están conectados.
Consulta el número de conjunto al que pertenece el elemento y devuélvelo directamenteidel valor del array,O(1)la complejidad temporal.
...
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
...
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
...
Fusionar el elementopy el elementoqdel conjunto al que pertenece; el proceso de unión requiere recorrer todos los elementos y luego fusionar los números de conjunto de los dos elementos; este proceso esO(n)la complejidad.
...
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
...
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
...
Código de ejemplo en Java
Descargar paquete de código fuente:Download
Código del archivo UnionFind1.java:
package ejemplo.union;
/**
* Primera versión de Union-Find
*/
public class UnionFind1 {
// Nuestra primera versión de Union-Find es esencialmente un array
private int[] id;
// Número de datos
private int count;
public UnionFind1(int n) {
count = n;
id = new int[n];
// Inicialización, cada id[i] apunta a sí mismo, no hay elementos fusionados
for (int i = 0; i < n; i++)
id[i] = i;
}
// Proceso de consulta, busca el número de conjunto correspondiente al elemento p
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
// Comprueba si el elemento p y el elemento q pertenecen al mismo conjunto
// Complejidad O(1)
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
// Fusiona el conjunto al que pertenecen el elemento p y el elemento q
// Complejidad O(n)
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
// El proceso de unión requiere recorrer todos los elementos y fusionar los números de conjunto de los dos elementos
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
}
/**
* Primera versión de Union-Find
*/
public class UnionFind1 {
// Nuestra primera versión de Union-Find es esencialmente un array
private int[] id;
// Número de datos
private int count;
public UnionFind1(int n) {
count = n;
id = new int[n];
// Inicialización, cada id[i] apunta a sí mismo, no hay elementos fusionados
for (int i = 0; i < n; i++)
id[i] = i;
}
// Proceso de consulta, busca el número de conjunto correspondiente al elemento p
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
// Comprueba si el elemento p y el elemento q pertenecen al mismo conjunto
// Complejidad O(1)
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
// Fusiona el conjunto al que pertenecen el elemento p y el elemento q
// Complejidad O(n)
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
// El proceso de unión requiere recorrer todos los elementos y fusionar los números de conjunto de los dos elementos
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
}