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 $\find(v)$ müssen wir also nur den $\parent$-Zeigern nachlaufen, bis wir an der Wurzel angelangt sind. Für $\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 $\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 $v$ merken wir seine Höhe $\height(v)$, also die Länge des längsten gerichteten Pfades $x \rightsquigarrow v$. Im unteren Bild haben also $e, c, b, g, f$ die Höhe $0$. Knoten $h$ hat Höhe 2. Knoten $i$ 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 $\rank(v)$ zu. Diesen initialisieren wir anfangs auf 2. Wenn wir $\union(u,v)$ ausführen, finden wir zuerst die Wurzeln der jeweiligen Bäume: $x := \find(u)$ und $y := \find(v)$. 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 $(x,y)$ ein und erhöhen den Rang von $y$ 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 $\rank$ im Prinip das Gleiche ist wie $\height$ (nur zwei mehr), warum führen wir also die neue Bezeichnung $\rank$ ein? Der Grund ist, dass wir später die Implementierung ändern und Zeiger umbiegen werden, wodurch sich $\height(v)$ ändert, nicht aber $\rank(v)$. Die Gleichung (\ref{rank-is-height}) 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 $u$ zur Wurzel $x$. Dies ist höchstens die Höhe des Baumes und somit höchstens $\rank(x) - 2$. Es stellt sich nun die Frage, wie groß $\rank(x)$ werden kann.

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

Am Anfang gilt $t=0$ und $\height_0(x) = 0$ und $\desc_0(x) = 1$ und die Aussage gilt. Die Anzahl der Nachfahren kann nur zunehmen, also $\desc_{t+1}(x) \geq \desc_t(x)$, also können wir uns auf die Zeitpunkte konzentrieren, wo $\height_t(x)$ zunimmt. Wann ist $\height_t(x) \lt \height_{t+1}(x)$? Dies kann nur geschehen, wenn in der $i+1$-ten union-Operation eine Kante $(y,x)$ eingefügt wird. Dann gilt

\begin{align*} \height_{t+1}(x) = \max(\height_t(x), \height_t(y) + 1) \end{align*}

Der Fall $\height_t(x) \lt \height_{t+1}(x)$ kann also nur auf folgende Weise geschehen: es wird eine Kante $(y,x)$ eingefügt und $\height_t(x) = \height_t(y) =: k$ und $\height_{t+1} (x) = k+1$. Nach Induktionshypothese gilt $\desc_t(x), \desc_t(y) \geq 2^k$. Da nach der union-Operation alle Elemente aus $T_y$ nun auch Nachfahren von $x$ sind, gilt

\begin{align*} \desc_{t+1}(x) = \desc_t(x) + \desc_t(y) \geq 2^k + 2^k = 2^{k+1} = 2^{\height_{t+1}(x)} \ , \end{align*}

und die Aussage des Lemmas gilt nach wie vor. \(\square\)

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

Kruskals Algorithmus benötigt somit $O((m+n) \log m)$ Schritte.

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