Union Find

Geschrieben von Joël Mathys.

Union Find

Das Problem von Union Find können wir uns gut anhand einer Party vorstellen. An jeder Party gibt es Leute aus verschiedenen Freundeskreisen. Ein Freundeskreis ist definiert als alle Personen, welche entweder direkt oder indirekt miteinander befreundet sind. Es kann deswegen gut sein, dass sich zwei Personen nicht direkt kennen, aber im gleichen Freundeskreis sind.

Die Partygäste sind als Knoten (Punkte) repräsentiert, die Freundschaft zwischen zwei Gästen als Kante zwischen den Knoten. In diesem Graphen gibt es drei Freundeskreise (weiss, grün, blau). In einem Freundeskreis können alle miteinander befreundet sein (weiss), müssen aber nicht (in blau kennt 5 6 nicht). Es kann auch Freundeskreise ohne Freundschaften (grün) geben.

Die Partygäste möchten ihren Freundeskreis möglichst erweitern. Dazu müssen sie wissen, ob sie sich im gleichen Freundeskreis befinden. Falls die beiden nicht im gleichen Freundeskreis sind, freunden sie sich (hoffentlich) an und erweitern somit ihren Freundeskreis.

Algorithmisch ausgedrückt: Wir möchten für zwei beliebige Knoten in einem Graph entscheiden, ob sie sich im gleichen Subgraphen (Freundeskreis) befinden unter der Voraussetzung, dass sich der Graph dynamisch ändern kann (Freundeskreise schliessen sich zusammen).

Lösungsansatz

Für jede Abfrage zweier Knoten können wir mit BFS oder DFS entscheiden, ob sie im gleichen Subgraphen sind. Um die Subgraphen allenfalls miteinander zu verbinden fügen wir einfach eine direkte Kante zwischen ihnen ein. Dieses Vorgehen kann zwar zwei Subgraphen in \(O(1)\) zusammenführen. Um zu entscheiden, ob zwei Knoten sich im gleichen Subgraphen befinden, braucht es aber immer eine Tiefen-/Breitensuche, welche eine Laufzeit von \(O(n+m)\) hat.

Für unseren Union Find Ansatz stellen wir uns folgendes vor: Jeder Subgraph bekommt genau einen Chef (jemanden den alle kennen). Wenn wir also entscheiden möchten, ob zwei Knoten im gleichen Subgraphen sind, können wir stattdessen ihre Chefs vergleichen.

vector<int> chef;
...
if(chef[a] == chef[b]){
    // gleicher Subgraph
}

Wenn wir zwei Subgraphen zusammenführen möchten, müssen wir einen neuen Chef bestimmen, da es nur einen Chef gaben kann. Dies würde eigentlich bedeuten, dass wir den Chef aller Knoten eines Subgraphen auf den Chef des anderen Subgraphen setzen müssten. Da wir aber durch alle Knoten gehen müssten, hätten wir eine Laufzeit von \(O(n)\). Stattdessen aktualisieren wir nur den Chef des einen Subgraphen. Wenn wir also Subgraph \(A\) (Chef \(a\)) mit Subgraph \(B\) (Chef \(b\)) verbinden möchten , setzten wir \(a\) als Chef von \(b\).

Anfangs ist jeder Chef von sich selbst. Wir betrachten die Knoten 2 und 4, ihre Chefs sind 2, resp. 4 d.h. sie sind in unterschiedlichen Subgraphen. Wenn wir die Subgraphen verbinden möchten setzten wir 4 als den Chef von 2 (roter Pfeil).

Dies bedeutet, dass wir den Chef eines Knotens nicht mehr direkt auslesen können, sondern suchen müssen. Dazu gehen wir solange zum jeweiligen Chef des Knotens, bis der Knoten der Chef von sich selbst ist.

In diesem Beispiel haben wir gerade den Subgraphen {0,1} mit dem Subgraphen {2,4} verbunden (roter Pfeil). Nun möchten wir wissen, ob 2 im gleichen Subgraphen ist wie 4. Dazu gehen wir erst von [1 -> 0 -> 2 -> 4 -> 4] => der oberste Chef von 1 ist 4. Das gleiche machen wir für 4 [4 -> 4] => der oberste Chef von 4 ist 4 => die beiden Knoten sind im selben Subgraphen.

vector<int> chef;
...
int find(int a){
    // wir sind selbst Chef, Ende der Suche
    if(a == chef[a]){
        return a;
    }
    // wir sind nicht selbst Chef,
    // also suchen wir bei unserem Chef weiter.
    return find(chef[a]);
}

Den Weg von \(x\) zum obersten Chef von \(x\) nennen wir einen Pfad. Jedes Mal, wenn wir wissen wollen, wer der Chef von \(a\) ist, müssen wir diesen Pfad entlang gehen und dementsprechend viele Funktionsaufrufe machen. Dies bedeutet im schlimmsten Fall haben wir immer \(O(n)\) Aufrufe um den Chef zu bestimmen. Mit einer kleinen Modifikation können wir dies aber deutlich verbessern. Statt jedes Mal den Chef zurückzugeben, speichern wir uns den Chef für den Knoten auch ab. Diesen Schritt nennen wir Path-Compression, da wir so die Länge des Pfades nach jedem Aufruf immer wieder auf 1 setzten.

Nachdem wir den Chef von 1 über den Pfad 1 -> 0 -> 2 ->4 gefunden haben, setzten wir 4 als direkten Vorgesetzten aller Knoten des Pfades.

Für unsere Modifikation müssen wir nur eine Codezeile ändern.

return chef[a] = find(chef[a]);

Um die beiden Subgraphen zu verbinden, müssen wir ihre Chefs aktualisieren. Dabei setzten wir den obersten Chef vom ersten Subgraphen auf den obersten Chef des zweiten Subgraphen.

void unite(int a, int b){
    a = find(a); // oberster Chef des Subgraphen a
    b = find(b); // oberster Chef des Subgraphen b
    chef[a] = b;
}

Um unsere Suche bei den find Funktionen noch etwas zu verbessern, müssten wir eigentlich unseren Baum balanciert halten. Dies ist aber relativ mühsam, deswegen können wir einfach die Subgraphen randomisiert einander zuweisen, d.h. der Zufall entscheidet ob \(a\) oder \(b\) der neue oberste Chef des Subgraphen wird. Man kann zeigen, dass die Randomisierung etwa gleich gut ist, wie balancieren (ist aber nicht SOI relevant).

void unite(int a, int b){
    a = find(a); // Chef des Subgraphen a
    b = find(b); // Chef des Subgraphen b
    // randomisierung
    if(randint()%2){
        chef[a] = b;
    }else{
        chef[b] = a;
    }
}

Implementierung

Laufzeit- und Speicheranalyse

  • find() und unite() haben dieselbe Laufzeit
  • Um den Chef eines Subgraphens zu suchen, ist die Laufzeit \(O(\alpha(n))\)
  • \(\alpha(n)\) ist die inverse Ackermann Funktion und für alle praktischen Werte unter 5 bleibt.
  • Es ist nicht wichtig, dass du die Ackermann Funktion oder dessen Laufzeitbeweis für Union Find kennst. Merke einfach, die Laufzeit von Union Find ist etwa \(O(1)\)

Code Beispiel C++

vector<int> chef;
int find(int a){
    if(a == chef[a]){
        return a;
    }
    return chef[a] = find(chef[a]);
}
void unite(int a, int b){
    a = find(a);
    b = find(b);
    if(randint()%2){
        chef[a] = b;
    }else{
        chef[b] = a;
    }
}
int init(){
    chef.clear();
    for(int i=0;i<n;i++){
        chef.push_back(i);
    }
}