Union Find

This wiki article doesn't exist in English. We will display it in German for you instead.

Written by Joël Mathys.

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)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)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)O(n). Stattdessen aktualisieren wir nur den Chef des einen Subgraphen. Wenn wir also Subgraph AA (Chef aa) mit Subgraph BB (Chef bb) verbinden möchten , setzten wir aa als Chef von bb.

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 xx zum obersten Chef von xx nennen wir einen Pfad. Jedes Mal, wenn wir wissen wollen, wer der Chef von aa ist, müssen wir diesen Pfad entlang gehen und dementsprechend viele Funktionsaufrufe machen. Dies bedeutet im schlimmsten Fall haben wir immer O(n)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;
}

Komponentengrösse abspeichern

Um unsere Suche bei den find Funktionen noch etwas zu verbessern, könnten wir unseren Baum balanciert halten. Wenn wir den Chef der kleineren Komponente auf die grössere zeigen lassen, dann bleiben die Pfade schön kurz.

Dafür könnte man ein zusätzliches Array mit der Grösse behalten. Oder, etwas einfacher, man könnte die Grösse als negativen Wert im Array abspeichern:

struct ufind {
  vector<int> c; // c=component (or chef)
  ufind(int n) : c(n, -1) {} // all components have size 1 (-> store -1)

  // negative value implies root
  int find(int k) { return c[k] < 0 ? k : (c[k] = find(c[k])); }

  void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;  // nothing to do (important to not add the size)
    if (c[a] > c[b]) swap(a, b); // we want b to be the smaller tree
    c[a] += c[b]; // add size of b to a
    c[b] = a;     // set parent of b to a
  }
};

Manchmal sieht man Code, der zufällig balanciert. Dies ist in der Theorie zwar asymptotisch gleich gut wie der Code oben, in der Praxis aber langsamer als nicht zu balancieren. Deshalb wird davon an dieser Stelle abgeraten.

Implementierung

Laufzeit- und Speicheranalyse

  • find() und unite() haben dieselbe Laufzeit
  • Um den Chef eines Knotens zu suchen, ist die Laufzeit:
    • O(α(n))O(\alpha(n)) wenn man nach Grösse balanciert. α(n)\alpha(n) ist die inverse Ackermann Funktion, welche extrem langsam wächst.
    • O(log(n))O(\log(n)) wenn man nicht balanciert.
  • In der Praxis ist Path-Compression ausreichend um durch das Time Limit zu kommen, aber es kann je nach Anwendung nützlich sein, die Komponentengrössen zu kennen.

Code Beispiel C++

struct ufind {
  vector<int> c;
  ufind(int n) : c(n) { iota(c.begin(), c.end(), 0); }
  int find(int k) { return c[k] == k ? k : (c[k] = find(c[k])); }
  void unite(int a, int b) { c[find(a)] = find(b); }
};