Estructura de datos Union-Find

Los artículos escritos en este blog fueron creados con el objetivo de enseñar. Además, la información del artículo puede ser incorrecta, así que tenga cuidado.

Union-Find es una estructura de datos que comprueba rápidamente si varios elementos pertenecen al mismo conjunto y combina dos conjuntos. Unión de conjuntos disjuntos, también llamada DSU para abreviar.

Buscar un representante como padre

class DisjointSet
{
public:
    explicit DisjointSet(int Count)
        : Parent(Count), Rank(Count, 0)
    {
        std::iota(Parent.begin(), Parent.end(), 0);
    }

    int Find(int Value)
    {
        if (Parent[Value] != Value)
        {
            Parent[Value] = Find(Parent[Value]);
        }

        return Parent[Value];
    }

    bool Unite(int A, int B)
    {
        A = Find(A);
        B = Find(B);

        if (A == B)
        {
            return false;
        }

        if (Rank[A] < Rank[B])
        {
            std::swap(A, B);
        }

        Parent[B] = A;

        if (Rank[A] == Rank[B])
        {
            ++Rank[A];
        }

        return true;
    }

private:
    std::vector<int> Parent;
    std::vector<int> Rank;
};

Path Compression conecta al padre directamente con el representante durante el proceso de búsqueda. Union by Rank evita que la profundidad aumente al colocar un árbol más bajo debajo de un árbol más alto.

Cuando ambas optimizaciones se utilizan juntas, la operación en realidad se comporta en un tiempo casi constante.

¿Dónde se usa?

• Compruebe si las dos regiones están conectadas.
• Compruebe si se produce un ciclo cuando se agrega un borde.
• Cree un árbol de expansión mínimo utilizando el algoritmo de Kruskal.
• Continúe combinando conjuntos en línea.

Union-Find no proporciona la ruta en sí. Es una estructura de datos poderosa cuando el propósito es la conexión o la fusión de conjuntos.