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 7.4.1 Sei $V$ eine Menge. Eine Partition von $V$ ist eine Menge $P$ von Teilmengen von $V$ mit folgenden zwei Eigenschaften:

\begin{aligned} (jedes Element kommt vor) & ⋃_{C \in P} C & = V \\ (die Teilmengen überschneiden sich nicht) & C_{1} \cap C_{2} & = \emptyset \forall C_{1} \neq C_{2} \in P \end{aligned}

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

auch nicht: 2 kommt zweimal vor.

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

: erstellt die (Repräsentation der) trivialen Partition , wo jedes Element in seiner eigenen Menge der Größe 1 enthalten ist.
: gibt die Menge aus, die 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.
: vereinigt die Mengen und 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 einen Kreis enthält, fragen wir . Wenn dies nicht der Fall ist und wir daher in Schritt 5 die Kante hinzufügen, dann führen wir 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 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 brauchen wir also nur einen Array-Zugriff. Für führen wir zweilmal aus und finden die entsprechenden Labels . Dann benennen wir alle Elemente mit Label um und geben ihnen Label . Damit wir hier nicht jedes Mal alle 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 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 Zeit. Eine Operation dagegen so viele, wie die Menge von Elemente hat. Im Worst-Case sind das .

Übungsaufgabe 7.4.1 Zeigen Sie, dass es eine Folge von union-Operationen gibt, für die die Datenstruktur UnionByLabel insgesamt 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 Schritten einen Pfad von nach zu suchen. Immerhin: Kruskal mit Tiefensuche in Zeile 4 braucht insgesamt Schritte, weil Zeile 4 mal ausgeführt wird. Mit unserer Datenstruktur kostet Zeile 4 nur , dafür müssen wir in Zeile 5 jedes Mal eine union-Operation ausführen. Glücklicherweise wird Zeile 5 ja nur mal ausgeführt. Daher:

Beobachtung 7.4.3 Die Laufzeit von Kruskals Algorithmus mit Tiefensuche in Schritt 4 ist . Mit UnionByLabel ist sie bzw. , 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 7.4.4 Die Datenstruktur RelabelMinority benötigt für eine Folge von union-Operationen höchstens Zeit. Eine find-Operation benötigt nach wie vor nur Schritte.

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

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

Wenn wir jedes individuell abschätzen, dann ist die optimale Abschätzung: es ist ja möglich, dass die Partition irgendwann ist und wir nun aufrufen, was in der Tat Schritte benötigt. Es ergäbe sich also eine Gesamtabschätzung von . Bei ist dies .

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 mit Zeilen und Spalten an. Die Zeilen sind indiziert mit den Elementen unseres Universums: . Die Spalten mit den Zeitpunkten der union-Operationen: . Wir setzen wenn Element in der -ten union-Operation ein neues Label zugewiesen bekommt und andernfalls. Der Wert ist somit die Summe der Einträge in der -ten Spalte.

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

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

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

Daher: eine Folge von union-Operationen kann benötigt höchstens Schritte.

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

Beobachtung 7.4.5 Kruskals Algorithmus führt find-Operationen und union-Operationen aus. Mit einer RelabelMinority-Datenstruktur benötigt das Schritte. Plus fürs Sortieren der Kanten.

Die Laufzeit wird also vom Sortieren der Kanten von billig nach teuer dominiert. Da wir im Allgemeinen das 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 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 in Rechnung gestellt.

Durch diesen Buchhaltertrick sind die Kosten für eine union-Operation von auf gesunken. Die Restkosten (Zeile 19) werden von den Elementen selbst übernommen. Wieviel Euro muss ein Element bezahlen? Wie oben gesehen wird höchstens mal umbenannt und muss daher maximal Euro bezahlen. Die Gesamtkosten belaufen sich bei find-Operationen und union-Operationen also auf

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