7. Graphen mit Kantenkosten

7.5 Union by Rank

Wir beschreiben nun eine neue Union-Find-Datenstruktur. Jede Menge der Partition wird durch einen Baum mit Wurzel dargestellt. In dem Baum sind alle Kanten zur Wurzel hin gerichtet. Implementieren lässt sich das einfach durch ein Array: parent[v] ist der Elternknoten von $v$; wenn $v$ selbst Wurzel ist, setzen wir parent[v] := v. Das Label einer Menge ist der Name des Wurzelknotens. Für $\text{find}(v)$ müssen wir also nur den $\text{parent}$-Zeigern nachlaufen, bis wir an der Wurzel angelangt sind. Für $\text{union}(u,v)$ finden wir erst einmal die jeweiligen Wurzeln $x$ und $y$ und hängen dann den einen Baum direkt an die Wurzel des anderen - setzen also $\text{parent}[x]:=y$. Oder umgekehrt. Wie sollen wir uns entscheiden? Die Datenstruktur RelabelMinority aus dem vorherigen Teilkapitel legt nahe, den kleineren Baum zum größeren zu verbinden. Wir tun hier etwas Ähnliches: wir verbinden den weniger tiefen Baum zum tieferen. Hier ist eine Demo:

Um das effizient zu implementieren, müssen wir etwas Buchführung treiben: für jeden Knoten $$ merken wir seine Höhe $$, also die Länge des längsten gerichteten Pfades $$. Im unteren Bild haben also $$ die Höhe $$. Knoten $$ hat Höhe 2. Knoten $$ hat mit 3 die größte Höhe aller Knoten.

Aus Gründen, die später noch klar werden werden, weisen wir jedem Knoten einen Rang $$ zu. Diesen initialisieren wir anfangs auf 2. Wenn wir $$ ausführen, finden wir zuerst die Wurzeln der jeweiligen Bäume: $$ und $$. Wir fügen nun eine Kante ein, von der Wurzel mit kleinerem Rang zu der mit größerem. Falls beide gleichen Rang haben, fügen wir die Kante $$ ein und erhöhen den Rang von $$ um eins. Der Kindknoten soll ja schließlich immer einen echt kleineren Rang haben als der Elternknoten. Hier sehen Sie meine Python-Implementierung:

class UnionByRank:
    def __init__(self, n):
        self.parent = [i for i in range(n)] # jedes Element ist Wurzel seines eigenen Baumes 
        self.rank = [2 for i in range(n)] # jedes Element hat Rang 2 

    def find(self,u):
        if self.parent[u] == u:
            return u 
        else:
            root = self.find(self.parent[u])
            return root
    
    def union(self, u, v):
        x = self.find(u)
        y = self.find(v)
        if (x == y):
            return # u, v sind bereits in der gleichen Menge 
        elif self.rank[x] < self.rank[y]:
            self.parent[x] = y 
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x 
        else: 
            self.parent[x] = y 
            self.rank[y] += 1

    def __str__(self):
        return (str(self.parent))

# example < < > > & & 

Nun könnten Sie sich fragen: wenn $$ im Prinip das Gleiche ist wie $$ (nur zwei mehr), warum führen wir also die neue Bezeichnung $$ ein? Der Grund ist, dass wir später die Implementierung ändern und Zeiger umbiegen werden, wodurch sich $$ ändert, nicht aber $$. Die Gleichung ($$) wird dann also nicht mehr gelten. Das obige Beispiel schaut also so aus:

Laufzeitanalyse

Die Laufzeit von find(u) ist proportional zur Länge des Pfades von $$ zur Wurzel $$. Dies ist höchstens die Höhe des Baumes und somit höchstens $$. Es stellt sich nun die Frage, wie groß $$ werden kann.

Beweis. Wir bezeichnen mit $$ die Höhe von $$ nach $$ union-Operationen. Mit $$ bezeichnen wir die Anzahl der Nachfahren zu diesem Zeitpunkt (als Abkürzung für descendants). Wir beweisen das Lemma mit Induktion über $$.

Am Anfang gilt $$ und $$ und $$ und die Aussage gilt. Die Anzahl der Nachfahren kann nur zunehmen, also $$, also können wir uns auf die Zeitpunkte konzentrieren, wo $$ zunimmt. Wann ist $$? Dies kann nur geschehen, wenn in der $$-ten union-Operation eine Kante $$ eingefügt wird. Dann gilt

$$

Der Fall $$ kann also nur auf folgende Weise geschehen: es wird eine Kante $$ eingefügt und $$ und $$. Nach Induktionshypothese gilt $$. Da nach der union-Operation alle Elemente aus $$ nun auch Nachfahren von $$ sind, gilt

$$

und die Aussage des Lemmas gilt nach wie vor. $$

Die Kosten einer jeden find-Operation sind also höchstens $$. Eine union-Operation besteht aus zwei find-Operationen plus $$ Rechenaufwand. Also gilt diese Schranke auch für sie.

Kruskals Algorithmus benötigt somit $$ Schritte.

Im Hinblick auf eine weitere Verbesserung im nächsten Teilkapitel zeigen wir eine weitere wichtige Eigenschaft der UnionByRank-Datenstruktur: