7. Graphen mit Kantenkosten

7.4 Union-Find-Datenstrukturen

Um Kruskals Algorithmus effizient implementieren zu können, brauchen wir eine Datenstruktur, die die Zusammenhangskomponenten von $(V,X)$ repräsentiert und folgende "Queries" unterstützt: (1) sameSet(u,v), die überprüft, ob $u$ und $v$ in der gleichen Komponente sind; dies soll die Frage beantworten, ob die Kante $\{u,v\}$ einen Kreis schließen würde. Und (2) connect(u,v), welche die Komponenten von $u$ und $v$ zu einer großen vereinigt; dies bilden ab, was geschieht, wenn wir die Kante $\{u,v\}$ hinzufügen. In der Literatur (und im Rest dieses Teilkapitels) werden jedoch andere Namen verwendet. Zu allererst brauchen wir den Begriff der Partition:

Definition Sei $V$ eine Menge. Eine Partition von $V$ ist eine Menge $\mathcal{P}$ von Teilmengen von $V$ mit folgenden zwei Eigenschaften:

\begin{align*} \bigcup_{C \in \mathcal{P}} C & = V \tag{jedes Element kommt vor} \\ C_1 \cap C_2 & = \emptyset \ \forall\ C_1 \ne C_2 \in \mathcal{P} \tag{die Teilmengen überschneiden sich nicht} \end{align*}

Hier ein paar Beispiele von Partitionen und Nicht-Partitionen der Menge $\{1,2,3,4,5,6,7,8\}$:

Die Menge $\{1,2,3,4,5,6,7,8\}$.

Die Partition $\{\{1,4,6\}, \{2,5,8\}, \{3,7\} \}$

Die Partition $\{\{1,6\}, \{4,8\}, \{2,7,5\}, \{3\} \}$

Die (triviale) Partition $\{\{1\},\{2\},\{3\},\{4\},\{5\},\{6\},\{7\},\{8\} \}$

Die (triviale) Partition $\{ \{1,2,3,4,5,6,7,8\} \}$

$\{\{1,2,6\}, \{4,5,3,7\}\}$ ist keine Partition: 8 fehlt

$\{ \{1,6,2,8\}, \{4,2,5\}, \{3,7\}\}$ auch nicht: 2 kommt zweimal vor.

Datenstrukturproblem - Union Find. Gewünscht ist eine Datenstruktur, die eine Partition auf einer Menge repräsentiert und folgende Operationen unterstützt:

${\rm init}(V)$: erstellt die (Repräsentation der) trivialen Partition $\{ \{v\} \ | \ v \in V\}$, wo jedes Element in seiner eigenen Menge der Größe 1 enthalten ist.
${\rm find}(u)$: gibt die Menge aus, die $u$ enthält; da es eine Partition ist, gibt es genau eine solche Menge. Streng genommen wird nicht die Menge selbst ausgegeben, sondern ein eindeutiges Label. Das Label ist im Prinzip beliebigt, wichtig ist nur, dass verschiedene Mengen verschiedene Labels erzeugen.
${\rm union}(u,v)$: vereinigt die Mengen ${\rm find}(u)$ und ${\rm find}(v)$ zu einer großen Menge; verändert also die Partition.

Eine Datenstruktur, die diese Operationen unterstützt, heißt Union-Find-Datenstruktur.

Mit einer Union-Find-Datenstruktur können wir Kruskals Algorithmus implementieren: um in Schritt 4 zu schauen, ob $X \cup \{u,v\}$ einen Kreis enthält, fragen wir ${\rm find}(u) \stackrel{?}{=} {\rm find}(v)$. Wenn dies nicht der Fall ist und wir daher in Schritt 5 die Kante $e = \{u,v\}$ hinzufügen, dann führen wir ${\rm union}(u,v)$ aus. Hier sehen Sie graphisch dargestellt, wie ich mir die Verwendung (nicht Implementierung) einer Union-Find-Datenstruktur vorstelle:

Die Datenstruktur Label-Rename

Ich stelle Ihnen jetzt eine erste Implementierung einer Union-Find-Datenstruktur vor. Es ist wahrscheinlich das erste, worauf die meisten Programmierer kommen würden. Der Einfachheit halber stelle ich mir die Elemente vor als Zahlen $0, \dots, n-1$ und verwende als Label für die Mengen auch diese Zahlen. Ich lege also ein Array label an, so dass jedes Element u in der Menge mit Label label[i] enthalten ist. Für $\find(u)$ brauchen wir also nur einen Array-Zugriff. Für $\union(u,v)$ führen wir zweilmal $\find$ aus und finden die entsprechenden Labels $l_1, l_2$. Dann benennen wir alle Elemente mit Label $l_1$ um und geben ihnen Label $l_2$. Damit wir hier nicht jedes Mal alle $n$ Elemente durchgehen müssen, speichern wir uns zu jedem Label noch eine Liste ab, in der die Elemente dieser Menge enthalten sind. Wir müssen also nur die Menge mit Label $l_1$ durchgehen.

class UnionByLabel:
    def __init__(self, n):
        self.label = [i for i in range(n)] # jedes Element i ist in einer Menge mit Label i
        self.set = [ [i] for i in range(n) ] # die Menge mit Label i besteht nur aus einem Element: i

    def find(self,u):
        return self.label[u]
    
    def union(self,u,v):
        l1 = self.find(u) # Das Label der Menge, die u enthält
        l2 = self.find(v) # Das Label der Menge, die v enthält

        if (l1 == l2):
            return

        set1 = self.set[l1] # Die Menge, die u enthält, als Liste
        set2 = self.set[l2] # Die Menge, die v enthält, als Liste

        for x in set1:
            self.label[x] = l2  # Allen Elementen aus set1 ein neues Label geben
        
        self.set[l2] += set1 # Die Menge mit Label l2 wird größer
        self.set[l1] = [] # Die Menge mit Label l1 verschwindet

    def __str__(self):
        return (str( [s for s in self.set if len(s) > 0]))

Eine find-Operation braucht also $O(1)$ Zeit. Eine Operation $\union(u,v)$ dagegen so viele, wie die Menge von $u$ Elemente hat. Im Worst-Case sind das $n$.

Übungsaufgabe Zeigen Sie, dass es eine Folge von $n$ union-Operationen gibt, für die die Datenstruktur UnionByLabel insgesamt $\Theta(n^2)$ Schritte braucht.

Es ist also eine nicht sehr effiziente Datenstruktur. Erinnerin Sie sich: die "Baseline" bei Kruskals Algorithmus ist ja mit Tiefensuche (oder Breitensuche) in $O(n)$ Schritten einen Pfad von $u$ nach $v$ zu suchen. Immerhin: Kruskal mit Tiefensuche in Zeile 4 braucht insgesamt $O(mn)$ Schritte, weil Zeile 4 $m$ mal ausgeführt wird. Mit unserer Datenstruktur kostet Zeile 4 nur $O(1)$, dafür müssen wir in Zeile 5 jedes Mal eine union-Operation ausführen. Glücklicherweise wird Zeile 5 ja nur $n-1$ mal ausgeführt. Daher:

Beobachtung Die Laufzeit von Kruskals Algorithmus mit Tiefensuche in Schritt 4 ist $O(mn)$. Mit UnionByLabel ist sie $O(n^2 + m)$ bzw. $O(n^2 + m \log m)$, wenn wir das Sortieren in Schritt 1 mitkalkulieren.

Unsere Implementierung von UnionByLabel ist verschwenderisch, weil wir immer unkritisch die Elemente der ersten Menge umbenennen. Sinnvoller wäre es, zu schauen, welche der beiden Mengen kleiner ist und dann die kleinere umzubennen. Wir nennen diese Implementierung RelabelMinority.

Theorem Die Datenstruktur RelabelMinority benötigt für eine Folge von $t$ union-Operationen höchstens $(n \log n + t)$ Zeit. Eine find-Operation benötigt nach wie vor nur $O(1)$ Schritte.

Beachten Sie, dass es gar nicht mehr als $n-1$ "richtige" Union-Operationen geben kann: bei jeder Operation, die zwei Mengen vereinigt, verringert sich die Anzahl der Mengen um 1.

Beweis. Wenn $u$ und $v$ in der gleichen Menge sind, dann benötigt $\union(u,v)$ nur $O(1)$ Schritte. Ansonsten ist die Anzahl der Schritte proportional zur Anzahl der Elemente, die umbenannt werden; also zur Größe der kleineren Menge. Bezeichne $a_j$ diese Anzahl in der $j$-ten union-Operation. Sei $a_j = 0$ wenn die $j$-te Operation gar nicht zwei Mengen vereinigt (weil eben $u$ und $v$ in der gleichen Menge sind). Die Gesamtlaufzeit ist also

\begin{align*} O\left(t + \sum_{j=1}^t a_j \right) \ . \end{align*}

Wenn wir jedes $a_j$ individuell abschätzen, dann ist $a_j \in O(n)$ die optimale Abschätzung: es ist ja möglich, dass die Partition irgendwann $\mathcal{P} = \{ \{1,\dots, n/2\}, \{n/2+1, \dots, n\}\}$ ist und wir nun $\union(1,n)$ aufrufen, was in der Tat $\Theta(n)$ Schritte benötigt. Es ergäbe sich also eine Gesamtabschätzung von $O(t + nt) = O(tn)$. Bei $t = n-1$ ist dies $O(n^2)$.

Um eine bessere Laufzeitabschätzgung zu erzielen, gehen wir anders vor. Die Haupteinsicht ist, dass nicht alle union-Operationen teuer sein können. Bei einer teuren union-Operation verschwindet eine bereits sehr große Menge in einer anderen (noch größeren). Dies kann nicht beliebig oft geschehen. Auf eine teure Operation müssen also viele billige kommen, was sich hoffentlich im Schnitt ausgleicht. Eine solche "ausgleichende" Analyse nennt man amortisierte Analyse. Ich werde zuerst einmal recht formal vorgehen und dann nochmal alles mit mehr Intuition durchgehen.

Wir legen eine Matrix $A$ mit $n$ Zeilen und $t$ Spalten an. Die Zeilen sind indiziert mit den Elementen $x$ unseres Universums: $1, 2, \dots, n$. Die Spalten mit den Zeitpunkten der union-Operationen: $1, \dots, t$. Wir setzen $a_{x,j} = 1$ wenn Element $x$ in der $j$-ten union-Operation ein neues Label zugewiesen bekommt und $a_{x,j} = 0$ andernfalls. Der Wert $a_j$ ist somit die Summe der Einträge in der $x$-ten Spalte.

Leere Einträge in der Matrix stehen für eine $0$. Hier noch einmal die endgültige Matrix $A$:

Wieviele Einträge hat Zeile $x$? So viele wie oft Element $x$ ein neues Label bekommen hat. Wie oft kann $x$ ein neues Label bekommen? Die naive Antwort: $n-1$ mal, denn ein Label (oben: Farbe) wird sich nie wiederholen; wenn es weg ist, ist es weg. Die bessere Antwort: wenn $x$ ein neues Label bekommt, dann bezeichne $S_x \in \mathcal{P}$ die Menge, die $x$ zuvor enthalten hat; die Menge $S_x$ wird mit einer anderen Menge $S_y$ vereinigt, und alle Elemente in $S_x$ (also auch $x$) bekommen das Label von $S_y$; nach diesem Schritt ist $x$ dann in der Menge $S_x \cup S_y \in \mathcal{P}$ enthalten. Da wir immer die Elemente aus der kleineren Menge umbennen, gilt $|S_x| \leq |S_y|$ und somit $|S_x \cup S_y| \geq 2 \cdot |S_x|$. Wir sehen: jedes Mal, wenn $x$ ein neues Label bekommt, wächst die Menge, die $x$ enthält, um mindestens eine Faktor von $2$. Nach $k$ Umbenennungegn hat sie also mindestens $2^k$ Elemente. Mehr als $n$ kann sie nicht haben, es gilt also $2^k \leq n$ und somit $k \leq \log n$: das Element $x$ kann höchstens $\log n$ mal umbenannt werden.

Wir haben also gerade gesehen: eine Spalte von $A$ kann zwar sehr wohl bis zu $n/2$ Einträge enthalten; eine Zeile aber höchstens $\log n$. Daher gilt:

\begin{align*} \sum_{x \in [n]} \underbrace{\sum_{j=1}^t A_{x,j}}_{\leq \log n} \leq \sum_{x \in [n]} \log n = n \log n \ . \end{align*}

Daher: eine Folge von $t$ union-Operationen kann benötigt höchstens $O(t + n \log n)$ Schritte.$\square$

Was bedeutet dies nun für die Laufzeit von Kruskals Algorithmus?

Beobachtung Kruskals Algorithmus führt $m$ find-Operationen und $n-1$ union-Operationen aus. Mit einer RelabelMinority-Datenstruktur benötigt das $O(m + n \log n)$ Schritte. Plus $O(m \log m)$ fürs Sortieren der Kanten.

Die Laufzeit wird also vom Sortieren der Kanten von billig nach teuer dominiert. Da wir im Allgemeinen das $O(m \log m)$ nicht schlagen können, könnten wir nun einpacken und nach Hause gehen. Allerdinsg könnte es ja sein, dass (1) die Kanten bereits sortiert vorliegen oder (2) die Kantenkosten kleine natürliche Zahlen sind und somit mit Bucketsort in linearer Zeit sortiert werden. Und generell ist die noch bessere Datenstruktur, die ich Ihnen in den nächsten zwei Teilkapiteln erklären werde, viel zu spannend, um das zu übergehen.

Laufzeitanalyse mit Geld-Metapher

Sie haben nun gerade eine amortisierte Laufzeitanalyse gesehen. Eine beliebte Metapher, um diese intuitiver zu machen, ist monetär: jeder Berechnungsschritt einen Euro kostet und muss von irgendjemanden bezahlt werden. Wir gehen wie folgt vor und beziehen uns auf den Python-Code von UnionByLabel:

find-Operationen verursachen Kosten von $O(1)$ Euro, die sie selbst tragen müssen.
eine union-Operation muss alles bis auf die Umbeschriftungs-Schritte in Zeile 19/20 (der Schleife for x in set1) tragen.
Die Kosten für Zeile 20 (self.label[x] = l2) werden dem Element $x$ in Rechnung gestellt.

Durch diesen Buchhaltertrick sind die Kosten für eine union-Operation von $O(\textnormal{Anzahl der Elemente, die umbenannt werden})$ auf $O(1)$ gesunken. Die Restkosten (Zeile 19) werden von den Elementen selbst übernommen. Wieviel Euro muss ein Element $x$ bezahlen? Wie oben gesehen wird $x$ höchstens $\log n$ mal umbenannt und muss daher maximal $\log n$ Euro bezahlen. Die Gesamtkosten belaufen sich bei $m$ find-Operationen und $t$ union-Operationen also auf

\begin{align*} O(\underbrace{m}_{\textnormal{find-Ops}} + \underbrace{n}_{\textnormal{union-Ops}} + n \underbrace{\log n}_{\textnormal{jedes einzelne Element}}) \end{align*}

Wir werden die Geld-Metapher nochmal in Kapitel 7.6 bemühen, wo wir eine deutlich anspruchsvollere Laufzeitanalyse durchführen.