data-structures
Union-find datastruktur

Introduktion

Teori

Unionen hittar datastrukturer som ger följande operationer:

• make_sets(n) initierar en facklig datastruktur med n singletons
• find(i) returnerar en representant för uppsättningen av elementet i
• union(i,j) sammanfogar seten som innehåller i och j

Vi representerar vår partition av elementen 0 till n - 1 genom att lagra ett överordnat element parent[i] för varje element i som så småningom leder till en representant för uppsättningen som innehåller i .
Om ett element i sig är ett representativt är det sin egen förälder, dvs parent[i] == i .

Således, om vi börjar med singletonsatser, är varje element sin egen representant:

Vi kan hitta representanten för en given uppsättning genom att helt enkelt följa dessa överordnade pekare.

Låt oss nu se hur vi kan slå samman uppsättningar:
Om vi vill slå samman elementen 0 och 1 och elementen 2 och 3 kan vi göra det genom att ställa in överordnade på 0 till 1 och ställa in överordnade på 2 till 3:

I detta enkla fall måste bara elementen föräldrarpekaren själv ändras.
Om vi emellertid vill slå samman större uppsättningar, måste vi alltid ändra föräldrarpekaren för representanten för den uppsättning som ska slås samman till en annan uppsättning: Efter sammanslagning (0,3) har vi ställt in föräldern till uppsättningens representant som innehåller 0 till representanten för uppsättningen som innehåller 3

För att göra exemplet lite mer intressant, låt oss nu också slå samman (4,5), (5,6) och (3,4) :

Den sista uppfattningen jag vill introducera är vägkomprimering :
Om vi vill hitta representanten för en uppsättning, kanske vi måste följa flera föräldrarpekare innan vi når representanten. Vi kan göra det lättare genom att lagra representanten för varje uppsättning direkt i deras överordnade nod. Vi förlorar ordningen i vilken vi slog samman elementen, men kan potentiellt ha en stor runtime-vinst. I vårt fall är de enda vägarna som inte komprimeras vägarna från 0, 4 och 5 till 3:

Grundläggande implementering

Den mest grundläggande genomförande av en unions hitta datastrukturen består av en array parent lagrar en överordnade elementet för varje del av strukturen. Efter dessa moder 'pekare' för ett element i leder oss till den representativa j = find(i) av uppsättningen innehåller i , där parent[j] = j innehar.

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;  // Parent for every node

public:
    union_find(size_t n) : parent(n) {
        for (size_t i = 0; i < n; ++i)
            parent[i] = i;      // Every element is its own representative
    }

    size_t find(size_t i) const {
        if (parent[i] == i)     // If we already have a representative
            return i;           // return it
        return find(parent[i]); // otherwise return the parent's representative
    }

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi != pj) {        // If the elements are not in the same set: 
            parent[pi] = pj;   // Join the sets by marking pj as pi's parent
        }
    }
};

Förbättringar: Väggkomprimering

Om vi gör många merge på en facklig datastruktur, kan banorna som representeras av parent pekare vara ganska långa. Bankomprimering , som redan beskrivits i teoridelen, är ett enkelt sätt att mildra denna fråga.

Vi kan försöka göra sökvägskomprimering på hela datastrukturen efter varje k- th-sammanslagningsoperation eller något liknande, men en sådan operation kan ha en ganska stor körtid.

Således används vägenkomprimering oftast bara på en liten del av strukturen, särskilt den väg vi går längs för att hitta representanten för en uppsättning. Detta kan göras genom att lagra resultatet av find drift efter varje rekursiv subcall:

size_t find(size_t i) const {
    if (parent[i] == i)          // If we already have a representative
        return i;                // return it
    parent[i] = find(parent[i]); // path-compress on the way to the representative
    return parent[i];            // and return it
}

Förbättringar: Union efter storlek

I vår nuvarande implementering av merge väljer vi alltid vänsteruppsättningen för att vara barn i rätt uppsättning utan att ta hänsyn till storleken på uppsättningarna. Utan denna begränsning kan vägarna (utan bankomprimering ) från ett element till dess representant vara ganska långa, vilket kan leda till stora körtider på find .

En annan vanlig förbättring är alltså unionen efter storleksheuristik , som gör exakt vad den säger: När vi sätter ihop två uppsättningar ställer vi alltid in den större uppsättningen för att vara överordnad till den mindre uppsättningen, vilket leder till en väglängd på högst steg:

Vi lagrar en ytterligare medlem std::vector<size_t> size i vår klass som initialiseras till 1 för varje element. Vid sammanslagning av två uppsättningar blir den större uppsättningen överordnad till den mindre uppsättningen och vi summerar de två storleken:

private:
    ...
    std::vector<size_t> size;

public:
    union_find(size_t n) : parent(n), size(n, 1) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {            // If the elements are in the same set: 
            return;                // do nothing
        }
        if (size[pi] > size[pj]) { // Swap representatives such that pj
            std::swap(pi, pj);     // represents the larger set
        }
        parent[pi] = pj;           // attach the smaller set to the larger one
        size[pj] += size[pi];      // update the size of the larger set
    }

Förbättringar: Union efter rang

En annan heuristik som vanligtvis används istället för union efter storlek är unionen efter rangheuristik

Dess grundläggande idé är att vi faktiskt inte behöver lagra den exakta storleken på uppsättningarna, en tillnärmning av storleken (i detta fall: ungefär logaritmen i uppsättningens storlek) räcker för att uppnå samma hastighet som förening efter storlek.

För detta introducerar vi begreppet rangordning för en uppsättning, som ges på följande sätt:

• Singletons har rang 0
• Om två uppsättningar med ojämn rang slås samman, blir uppsättningen med större rang överordnad medan rankingen är oförändrad.
• Om två uppsättningar av lika rang sammanfogas blir den ena föräldern till den andra (valet kan vara godtyckligt), dess rang ökas.

En fördel med förening efter rang är rymdanvändningen: Eftersom den maximala rankningen ökar ungefär som , för alla realistiska inmatningsstorlekar, kan rankningen lagras i en enda byte (eftersom n < 2^255 ).

En enkel implementering av unionen efter rang kan se ut så här:

private:
    ...
    std::vector<unsigned char> rank;

public:
    union_find(size_t n) : parent(n), rank(n, 0) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {
            return;
        }
        if (rank[pi] < rank[pj]) {
            // link the smaller group to the larger one
            parent[pi] = pj;
        } else if (rank[pi] > rank[pj]) {
            // link the smaller group to the larger one
            parent[pj] = pi;
        } else {
            // equal rank: link arbitrarily and increase rank
            parent[pj] = pi;
            ++rank[pi];
        }
    }

Slutlig förbättring: Union efter rang med lagring utanför gränserna

I kombination med bankomprimering uppnår ungefärlig rang nästan konstant tidsoperationer på fackliga fynd-datastrukturer, det finns ett sista trick som gör att vi kan bli av med rank helt och hållet genom att lagra rankningen i poster utanför gränserna för parent . Det är baserat på följande observationer:

• Vi behöver faktiskt bara lagra rankningen för representanter , inte för andra element. För dessa representanter behöver vi inte lagra en parent .
• Hittills är parent[i] högst size - 1 , dvs. större värden är oanvända.
• Alla rankningar är högst .

Detta leder oss till följande strategi:

• Istället för villkorsföräldern parent[i] == i , identifierar vi nu representanter av
  parent[i] >= size
• Vi använder dessa out-of-bound-värden för att lagra uppsättningen, dvs. setet med representant i har rangordnad parent[i] - size
• Således initialiserar vi överordnade array med parent[i] = size istället för parent[i] = i , dvs varje uppsättning är sin egen representant med rang 0.

Eftersom vi bara kompenserar för rankningsvärdena efter size kan vi helt enkelt ersätta rank med parent vektor vid implementeringen av merge och bara behöver utbyta villkor som identifierar representanter i find :

Färdig implementering med hjälp av union efter rang- och sökkomprimering:

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;

public:
    union_find(size_t n) : parent(n, n) {} // initialize with parent[i] = n

    size_t find(size_t i) const {
        if (parent[i] >= parent.size()) // If we already have a representative
            return i;                   // return it
        return find(parent[i]);         // otherwise return the parent's repr.
    }

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {
            return;
        }
        if (parent[pi] < parent[pj]) {
            // link the smaller group to the larger one
            parent[pi] = pj;
        } else if (parent[pi] > parent[pj]) {
            // link the smaller group to the larger one
            parent[pj] = pi;
        } else {
            // equal rank: link arbitrarily and increase rank
            parent[pj] = pi;
            ++parent[pi];
        }
    }
};