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];
}
...

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;
}
...

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;
    }
}
Otras extensiones