Herzlich willkommen zur Vorlesung.
Heute wollen wir uns mit minimalen Spannbäumen beschäftigen.
Das heißt, von einem Grafen mit Kantengewichten, ein Teilgraf, der ein
Baum ist, sodass die Summe der Gewichte über diesen Baum besonders
klein ist, eben ein minimaler Spannbaum.
Und ich weiß nicht, ob da wirklich ein toller Zusammenhang ist, aber
man könnte sich das vielleicht auch so vorstellen, dass man hier
irgendwelche Reiserouten entwerfen will, sodass man möglichst wenig
Proviant an Bord haben muss und dann auf den Inseln eben immer wieder
nachladen kann.
Also, wie ich sagte, die Eingabe ist ein ungerichteter Zusammenhängen
der Graf, zusammenhängend, bitte, damit wir von überall nach überall
kommen überhaupt, mit den Knoten, der Knotenmenge V.
Es gibt N Knoten, wie immer.
Wir könnten uns zum Beispiel vorstellen, dass wir die Knoten auch 1
bis N nennen.
Die Kantenmengen sind Paare von Knoten.
Es gibt M Kanten.
Und es gibt eine Funktion, Kosten von E, C von E, die gibt uns das
Kantengewicht an.
Das kann man sich so vorstellen, wie eben eine Entfernung bei einem
Grafen oder eben wie viel Proviant man braucht, um von der einen Insel
auf die andere Insel zu kommen.
Hier sehen wir etwas.
Das sind sozusagen 4 Knoten, 4 Kanten.
Und der minimale Spannbaum wäre jetzt hier, das da.
Das heißt, wir würden diese teure Kante dort einfach weglassen.
Wenn wir noch eine Kante weglassen würden, würde das Ding zerfallen.
Es wäre kein Spannbaum mehr.
Das heißt, wir würden mit unserem Baum gar nicht mehr alle Knoten
erreichen.
Aber diese Kante, die liegt auf einem Kreis.
Kreise brauchen wir nicht in Bäumen.
Können wir weglassen.
Und deshalb wäre hier ein minimaler Spannbaum und das sind tatsächlich
diese Konstruktionen.
Das heißt, die Aufgabe ist jetzt, finde zu dieser Eingabe einen Baum,
T, mit minimalem Gewicht.
Wobei das minimale Gewicht heißt, dass die Summe über alle Gewichte im
Baum minimal sein soll.
Der außerdem bitte alle Knoten verbindet.
Ein Spannbaum eben ist.
Falls der Graph nicht zusammenhängend ist, kann man das leicht
erweitern auf minimale aufspannende Wälder.
Das heißt, dann würde man jede Zusammenhangskomponente für sich
betrachten.
Dort einen minimalen Spannbaum suchen.
Und dann kann man sozusagen den minimalen Spannbaum-Algorithmus leicht
verallgemeinern.
Und so eben Zusammenhangskomponente für Zusammenhangskomponente eben
einen minimalen Spannbaum finden, um dann einen minimalen Spannwald zu
haben.
Anwendungen im Netzwerkentwurf.
Man kann sich sicher vorstellen, dass wenn man ein Netzwerk bauen
will, wo man von jedem Knoten zu jedem Knoten telefonieren kann, aber
die Kantengewichte sind vielleicht die Kosten für das Einrichten der
Leitung, dann wäre ein minimaler Spannbaum genau das Richtige.
Die Summe über die Kosten ist minimal und wir erreichen immer noch
jeden Teilnehmer im Netzwerk.
Etwas interessanter vielleicht, weil nicht ganz so trivial ist, die
Bottleneck Shortest Path.
Das heißt, wir suchen zwischen einem Start- und einem Zielknoten einen
ST -Pfad, dessen maximales Kantengewicht minimal ist.
Das heißt, wir interessieren uns dafür, dass dieses maximale Gewicht,
das auf dem Pfad irgendwo auftritt, das ist sozusagen das Maß, für das
wir uns interessieren.
Und das soll jetzt auf einmal minimal werden.
Man kann sich zum Beispiel vorstellen, dass solche großen Kosten
irgendwie eine Art Bottleneck sind.
Das heißt, solche großen Kosten wollen wir auf jeden Fall vermeiden.
Und dann ist das Tolle, dieser Pfad, der sozusagen das kleinste
Maximum hat, ist tatsächlich ein Pfad im minimalen Spannbaum.
Und das ist schon ein nicht ganz trivialer Zusammenhang.
Und weitere Anwendungen sind beispielsweise Clustering.
Man hat eine Punktwolke und wir betrachten jetzt tatsächlich mal den
Abstand im euklidischen Raum als Kosten und haben vielleicht einen
hochdimensionalen Raum und der Abstand ist die Kostenfunktion.
Jetzt könnte man erstmal einen minimalen Spannbaum bauen und sich dann
eben die Kosten angucken.
Und wenn man jetzt sehr, sehr schwere, sprich sehr, sehr lange Kanten
weglässt, dann zerfällt auf einmal das Ding in Cluster von nahe
beieinanderliegenden Punkten.
Tolle Sache.
Das kann man zum Beispiel in der Bildsegmentierung, also in der
Bildverarbeitung benötigen, aber vielleicht auch, wenn man Outlier
Detection macht, da würde man vielleicht irgendwie ein Clustering
machen wollen und dann gucken, wer liegt denn da alleine draußen.
Und dann kann man minimale Spannbäume auch benutzen als Nährungslösung
für an sich schwere Probleme, zum Beispiel das handlungsreißende
Problem oder das Steinerbaum-Problem.
Das werden wir hier aber nicht weiter vertiefen.
Und es gibt da eine Methode, das kann man irgendwie bei Wikipedia
nachlesen, wie man Irrgärten so darstellen kann, dass irgendwie die
Lösungspfade die kürzesten Pfade sind und dann kann man eben mit einem
minimalen Spannbaum da Lösungen finden.
Wobei das Lösungen sind unter der Kategorie ich suche Lösungswege,
wenn ich den gesamten Irrgarten kenne.
Es gibt ja auch das Problem, dass ich einen Weg nach draußen suche und
ich kenne nicht den gesamten Irrgarten.
Da gibt es dann zum Beispiel diese rechte Handregel, dass man mit der
rechten Hand die Wand anfasst und einfach langfährt.
Und wenn man das zum Beispiel von Anfang an gemacht hat, dann kommt
man garantiert wieder raus.
Wenn man im Innern des Irrgartens damit anfängt, ist es nicht klar,
dass man damit wieder rauskommt.
Das erinnert nämlich an diesen Witz von dem Betrunkenen, der an die
Litfaßsäule stößt, sich drum herumtastet und irgendwann sagt Scheiße,
eingemauert.
Also wie gesagt, im Innern des Irrgartens kann es sein, dass man da im
Kreis läuft und nicht rausfindet.
Genau.
So.
Wenn wir minimale Spannbäume finden wollen, dann brauchen wir so ein
paar Regeln, damit wir sehen können, welche Kanten wir bitte auswählen
sollten und welche Kanten wir bitte verwerfen sollten.
Und eine Eigenschaft, die wir hier beachten werden, ist die
Schnitteigenschaft.
Wenn wir eine Teilmenge S der Knotenmenge haben, dann sind die
Schnittkanten die, die von der Menge S rausgehen außerhalb der Menge
S.
Eine Schnittkante ist für uns eine Kante, die einen Knoten von
innerhalb der Menge S mit einem Knoten außerhalb der Menge S
verbindet.
Und jetzt ist es so, wenn wir für irgendeine beliebige Teilmenge S die
Menge der Schnittkanten betrachten, also alle die Kanten, die in S
anfangen und nach außerhalb von S führen, dann ist es so, dass die
leichteste Kante in dieser Schnittkantenmenge, die darf man in einem
minimalen Spannbaum verwenden.
Warum muss man nicht?
Warum darf man nur?
Es kann ja sein, dass es mehrere Lösungen gibt.
Auf jeden Fall führt das zu einer Lösung, wenn wir diese leichteste
Kante verwenden.
Das kann man relativ leicht, hier ist ein Beispiel, also hier ist so
ein Schnitt, das heißt wir können uns zum Beispiel vorstellen, dass
die Menge S nur aus dem Knoten 2 besteht und dann ist das hier die
leichteste Kante, die leichteste Schnittkante.
Man kann das leicht einsehen, dass das immer so ist.
Beweis betrachte einen minimalen Spannbaum T'.
Falls die Kante E, die wir im Spannbaum verwenden dürfen, schon Teil
des Spannbaums ist, dann ist der Beweis auch schon fertig.
Was zu tun ist, wenn wir tatsächlich einen Spannbaum gefunden haben,
wo diese Kante E nicht drin ist, dann können wir T', aber um E
anreichern.
Jetzt hat das Ding einen Kreis und wir betrachten eine Kante UV, die
eine Schnittkante ist und
in dem Kreis liegt, aber nicht die Kante E selber ist.
Dann können wir sozusagen einen neuen Spannbaum betrachten und dieser
neue Spannbaum besteht daraus, dass wir jetzt diese eine Kante aus dem
Kreis rausnehmen und die Kante E hinzufügen und dieser Spannbaum wird
dadurch nicht schwerer.
Warum wird er nicht schwerer?
Weil hier die Kante E verbindet die Menge S mit der Menge außerhalb
von S und das war die leichteste Kante und wenn wir jetzt die Kante,
die der andere minimale Spannbaum genommen hat, durch die leichteste
Kante ersetzen, dann darf der Spannbaum nicht schwerer werden, weil
diese Kante hier höchstens schwerer sein könnte, aber wenn sie echt
schwerer gewesen wäre, dann wäre das überhaupt kein minimaler
Spannbaum gewesen.
Deshalb bleibt das hier alles gleich und wir haben sozusagen diese
Verbindungslinie der beiden Teilmengen ersetzt durch jene
Verbindungslinien der beiden Teilmengen.
Das heißt, wir haben jetzt einen anderen minimalen Spannbaum, der
jetzt diese Kante E tatsächlich verwendet.
Es gibt noch eine zweite Eigenschaft.
Die eine Eigenschaft ist, dass wir für jede Teilmenge von den
Querschnittskanten die leichteste verwenden dürfen.
Eine andere Eigenschaft, die erlaubt es uns, Dinge zu verwerfen, die
schwerste Kante auf einem Kreis wird nicht für einen minimalen
Spannbaum benötigt.
Das heißt, wenn wir irgendwo einen Kreis haben, das war unser Beispiel
vom Anfang, das war tatsächlich schon ein Kreis, und die schwerste
Kante hier, die können wir einfach weglassen und sind uns sicher, dass
wir ohne diese Kante einen minimalen Spannbaum finden.
Auch das ist wieder relativ leicht einzusehen.
Angenommen, ein minimaler Spannbaum T', benutzt die schwerste Kante
tatsächlich.
Dann existiert eine Kante aus dem Kreis, die nicht im Spannbaum ist,
sodass, wenn wir jetzt diese schwerste Kante ersetzen durch die andere
Kante, es auch ein minimaler Spannbaum ist.
Ja, wir haben sozusagen den Kreis geschlossen und dann an der
schwersten Kante wieder aufgerissen.
Das heißt, es muss dann auf jeden Fall, weil das auch ein minimaler
Spannbaum ist, muss das Gewicht von der neuen Kante kleiner, denn es
gilt, dass das Gewicht von der neuen Kante kleiner gleich ist, denn E
-Strich war ja die schwerste Kante.
Also wenn wir jetzt den Kreis erst vervollständigen und dann die
schwerste Kante rausnehmen, dann haben wir, wenn es vorher ein
minimaler Spannbaum war, hinterher auf jeden Fall auch einen minimalen
Spannbaum, denn wir haben es ja höchstens leichter gemacht.
Und jetzt kann man mit diesen beiden Einsichten quasi schon einen
Algorithmus vorschlagen.
Das ist der Janik-Prim-Algorithmus.
Und die Idee ist, wir lassen einen Baum wachsen, und zwar beginnen wir
mit einem leeren Spannbaum und mit einer Menge S, die nur einen
Startknoten enthält, wobei es im Moment egal ist, mit welchem
Startknoten wir anfangen, weil jeder Knoten auf dem minimalen
Spannbaum liegt, können wir irgendwo anfangen.
Und jetzt wiederholen wir die Anzahl der Knoten minus eins mal
Folgendes.
Für das S, das wir im Moment haben, ganz am Anfang enthält das nur den
Startknoten, finden wir eine Kante UV, die diese Schnitteigenschaft
hat.
Das heißt, sie führt von S nach außerhalb von S und hat minimales
Gewicht.
Wenn wir so eine gefunden haben, dann werden wir sagen, die nehmen wir
zu unserem Spannbaum hinzu und außerdem nehmen wir den Zielknoten V zu
unserer Menge S hinzu, weil der jetzt zu dem schon gefundenen, schon
erschlossenen Knoten dazugehört.
Das heißt, wenn wir jetzt anfangen würden beispielsweise hier mit dem
Startknoten A, dann würden wir hier einen Schnitt reinlegen und die
Schnittkante mit dem geringsten Gewicht ist die mit Gewicht 6, die
nehmen wir jetzt zu unserem Spannbaum hinzu und den Knoten C nehmen
wir zu unserer Menge S hinzu.
Deshalb ist der nächste Schnitt, dass wir A und C in der Menge S links
haben und B und D außerhalb.
Und von den Kanten, die über diesen Schnitt hinübergehen, von den
Schnittkanten, die wir schneiden, ist die mit Gewicht 3 die
leichteste.
Die nehmen wir zu unserem Spannbaum hinzu und die Menge B, den Knoten
B, nehmen wir in die Menge S hinein.
Das heißt, S umfasst jetzt A, B, C.
Das heißt, der Schnitt zwischen S und außerhalb von S geht jetzt hier
lang.
Es gibt drei Schnittkanten.
Die leichteste davon ist die mit Gewicht 2.
Die nehmen wir zu unserem Spannbaum hinzu.
Und weil wir jetzt 4 minus 1, also drei Schritte gemacht haben, sind
wir auch schon fertig, denn wir haben tatsächlich alle Knoten
verbunden.
Jedes Mal, wenn der Algorithmus hier durchgeht, wird ein neuer Knoten
durch den Spannbaum neu verbunden.
Das heißt, der Spannbaum hat nach N minus 1 Durchgängen N Knoten, denn
mit einem starten wir schon.
Wenn man das jetzt von dem sehr highleveligen Pseudocode-Betrachtung
etwas konkreter machen will, dann kriegen wir Janik Prim Minimal
Spanning Tree JP MST sehr ähnlich zum Dijkstra-Algorithmus.
Wir nehmen am Anfang irgendeinen Startknoten, dann sind alle Distanzen
das ist ein Distanz-Array am Anfang unendlich und Parent von S ist S
das heißt, damit markieren wir wieder, dass das der Startknoten ist.
Die Distanz von S zu S ist Null, wir sind schon da und wir nehmen eine
Priority Queue, in die wir S einfügen.
Und dann der Algorithmus, solange die Priority Queue nicht leer
geworden ist, machen wir folgendes, wir nehmen uns den Knoten mit dem
geringsten Gewicht aus der Priority Queue wir setzen dieses Gewicht
jetzt künstlich auf Null, weil wir da schon gerade sind und jetzt
scannen wir U das heißt, für jede Kante die von U nach V geht schauen
wir, ob die Kosten dieser Kante kleiner sind als die bisher schon
errechneten Kosten um den Knoten V zu erreichen.
Falls ja, dann setzen wir D von V zu diesen neuen Kosten und wir
sagen, Parent von V ist U das heißt tatsächlich werden wir jetzt vom
Spannbaum her U und V direkt verbinden.
Falls V in der Prioritätsliste schon drinnen war, dann machen wir
Decrease Key das heißt, der kriegt jetzt ein niedrigeres Gewicht
ansonsten fügen wir ihn in die
Prioritätsliste hinein und wenn wir damit durch sind wenn die
Prioritätsliste irgendwann mal leer ist dann geben wir zurück
einen Knoten V nein, wir geben die für alle V aus V Paare zurück, das
ist nämlich V und Parent von V und diese Knotenpaare bilden genau den
Spannbaum ein Spannbaum ist auch ein Graph, ist also eine Menge von
Paaren und das sind genau die Paare, die wir hier ausgerechnet haben
die Idee ist dass wir das Gewicht von U also die Distanz U auf 0
setzen genau dann, wenn U in unserer Menge S drin ist und am Ende
jeder While-Iteration
dieses D von V wenn es nicht 0 ist wenn es 0 ist, ist es ja in der
Menge S drin wenn es aber nicht 0 ist und hat das geringste Gewicht
dann ist es genau das Gewicht der leichtesten Kante die zu dem V das
nicht in S ist sonst wäre ja D von V 0 über den Schnitt führt das
heißt, das ist der nächste Knoten zu dem wir hingehen in unserem
Spannbaum das erklärt sozusagen warum man hier in dem Moment D von U
auf 0 setzt weil man in dem Moment sagt, jetzt gehört das zur Menge S
dazu und die
Priority Queue hat die
Knoten gespeichert, die noch nicht auf 0 gesetzt sind davon nehmen wir
sozusagen den kleinsten Baus und bauen so den Baum konkret auf nach
diesem Algorithmus bloß, dass wir dieses Finde-UV-Fulfilling-the-Cut
-Property geschickt implementiert haben durch eine Priority Queue die
uns immer den Knoten finden lässt zu dem wir als nächstes gehen müssen
um außerhalb der Menge S die geringsten Kosten zu haben
die Analyse von diesem Algorithmus ist sehr ähnlich dem Dijkstra
-Algorithmus mit Priority Queues das heißt Wir verbrauchen O von M
plus N Zeit außerhalb der Priority Queue.
Wenn wir mal die Kosten der Priority Queue immer als konstant ansehen
würden.
Wir machen N mal DeleteMin.
Das hat eine Zeit von O von N log N.
Also DeleteMin war log N und das machen wir N mal.
Das heißt O von N log N.
Wir machen O von M mal DecreaseKey.
Das ist O von M.
Das heißt insgesamt haben wir O von M plus N mal log N mit den Binary
Heaps, die wir kennen.
Und wir können hier beim DecreaseKey den Logfaktor sparen, wenn wir
abgefahrenere Heaps verwenden würden.
Ein wichtiger Unterschied ist, monotone Priority Queues, die wir beim
Dijkstra -Algorithmus noch verwenden durften zur weiteren Optimierung,
die dürfen wir hier nicht mehr verwenden.
Und ich denke, dass dieses Anpassen der Gewichte, wenn man das
durchgeht, nicht mehr garantiert monoton ist.
Und deshalb wir diese Optimierung eben nicht verwenden dürfen.
Gut.
Interessant ist, dass es einen zweiten Algorithmus gibt, der minimale
Spannbäume findet.
Und dann kann man sich hinterher überlegen, welchen man lieber hat.
Wir werden die beiden noch vergleichen.
Der ist auf jeden Fall sehr anschaulich hier.
Und zwar ist die Idee die, dass wir sagen, wir haben einen Subwald des
Spannbaums schon gefunden.
Und jetzt suchen wir eine Kante, um zwei von den Bäumen zu verbinden.
Also wir haben einen Subwald des Spannbaums schon gefunden.
Und jetzt suchen wir eine Kante, die zwei von den Bäumen verbindet.
Wenn diese Kante nicht zwei von den Bäumen verbindet, dann schließt
sie irgendwo einen Kreis.
Das können wir nicht brauchen.
Sondern wir suchen eine Kante, die zwei solcher Bäume verbindet.
Von dem Teil Wald, das Minimal Spanning Tree, den wir schon gefunden
haben.
Und das Tolle ist, wir können dann einfach die leichteste Kante
nehmen.
Denn wenn wir den Baum, den wir verbinden, in die Menge S tun, also
den einen Baum, den wir verbinden, in die Menge S, den anderen Baum
außerhalb, wohin wir die anderen Bäume packen, ist relativ egal, dann
haben wir eine Kante hier, die die Menge S mit außerhalb von S
verbindet.
Es ist die leichteste Kante, deshalb dürfen wir sie hinzunehmen.
Das heißt, für jedes UV in der Kantenmenge, die wir in aufsteigender
Ordnung des Gewichtes vorsortiert haben, gucken wir einfach, ob UV
verschiedene Teilbäume verbindet.
Dann nehmen wir sie hinzu und wenn nicht, nehmen wir die nächste.
Also man kann sich das so vorstellen, hier ganz am Anfang sind alle
Knoten einzelne Teilbäume für sich.
Dann nehmen wir einfach die leichteste Kante überhaupt und gucken,
verbindet diese leichteste Kante überhaupt zwei Teilbäume?
O ja, B und D sind bisher noch nicht verbunden, nehmen wir hinzu.
Dann schauen wir uns die nächstleichteste Kante an, das ist die Kante
mit Gewicht 3, und wir fragen uns, hey, verbindet diese Kante zwei
bisher noch nicht verbundene Teilbäume?
O ja, der Teilbaum B, D und der Teilbaum C, der noch für sich ganz
alleine steht, die sind noch nicht verbunden, das heißt, diese Kante
dürfen wir hinzunehmen.
Jetzt nehmen wir die nächstleichteste Kante, das ist diese Viererkante
hier, und stellen fest, oh nein, die verbindet nicht zwei bisher nicht
verbundene Teilbäume, sondern die schließt da einen Kreis, die können
wir nicht gut brauchen.
Dann nehmen wir demzufolge die nächste vom Gewicht her, das wäre hier
diese Kante vom Gewicht 6, und die A tatsächlich verbindet zwei bisher
noch nicht verbundene Teilbäume, die nehmen wir hinzu, und wir haben
unseren minimalen Spannbaum gefunden.
Also, warum ist das korrekt?
Ich habe es schon angedeutet.
Und wir machen weiter, und zwar ganz einfach.
Kruskalls Algorithmus, wir betrachten alle Kanten sortiert nach
Gewichten, und für jede Kante, wir nehmen immer die leichteste,
betrachten die leichteste Kante, gucken wir, ob diese Kante zwei
Teilbäume verbindet.
Wenn ja, nehmen wir diese Kante zu unserem Spannbaum hinzu.
Wenn nein, dann schließt sie einen Kreis, und wir nehmen sie nicht
hinzu.
Warum dürfen wir das?
Warum führt das zum richtigen Ergebnis?
Falls UV, die Kante, die wir betrachten, die leichteste Kante, die
noch zu betrachten ist,
in verschiedenen Teilbäumen liegt, dann können wir die
Schnitteigenschaft benutzen, weil wir einfach den einen Teilbaum in
die Menge S packen, den anderen Teilbaum außerhalb der Menge S, wo wir
die anderen Teilbäume verteilen, ist relativ egal, dann haben wir da
einen Schnitt, und diese Kante ist, weil es die leichteste Kante ist,
die wir betrachten, auch die leichteste Kante, die über diesen Schnitt
überhaupt geht.
Alle anderen Kanten sind schwerer.
Und weil es die leichteste Kante über einen Schnitt ist, dürfen wir
sie im minimalen Spannbaum verwenden.
Falls eine Kante einen Kreis schließt, dann sind alle anderen Kanten
leichter, denn die haben wir davor schon betrachtet.
Das heißt, eine Kante, die einen Kreis schließt, ist die schwerste
Kante in dem Kreis, und die dürfen wir auch weglassen.
Das ist die Kreiseigenschaft.
Und damit ist klar, dass der Algorithmus uns einen minimalen Spannbaum
liefern wird.
Jede Kante, die er aufnimmt, ist eine Kante, die wir nach
Schnitteigenschaft verwenden dürfen, und jede Kante, die er verwirft,
ist eine schwerste Kante im Kreis, und die dürfen wir auch verwerfen.
Jetzt ist es bloß so, dieser Algorithmus ist sehr, sehr high-level
beschrieben.
Wir brauchen jetzt noch eine irgendwie geartete, pfiffige
Datenstruktur, um schnell zu erkennen, ob U und V in verschiedenen
Teilbäumen liegen.
Wir brauchen eine effiziente Methode für die Frage, verbindet diese
Kante tatsächlich verschiedene Teilbäume?
Und was wir dafür einführen werden, ist die Union-Find-Datenstruktur.
Die Union-Find-Datenstruktur verwaltet Partitionen der Menge von 1 bis
N.
Eine Partition ist eine Menge von Mengen, die wir manchmal vielleicht
auch einfach Blöcke nennen werden, sodass alle diese Mengen vereinigt
ist die gesamte Menge, und je zwei der Blöcke haben leeren Schnitt,
die sind disjunkt, und eine solche Zerlegung einer Menge in disjunkte
Teilmengen nennen wir eben eine Partition.
Da ist eine Partition bildlich dargestellt.
Union-Find erlaubt uns jetzt zwei Operationen, nämlich Union und Find.
Die Procedure Union gibt uns zwei Elemente und falls die eben in
verschiedenen Blöcken sind, verbindet Union diese Blöcke zu einem
Block.
Union macht aus zwei solchen Blöcken einen Block und Find nimmt ein
Element und gibt uns zurück einen eindeutigen Namen, einen eindeutigen
Identifier für den Block, der dieses Element enthält.
Und damit können wir dann eben die Teilbäume, die wir schon gefunden
haben, als Blöcke betrachten.
Zu jedem Element finden wir schnell den Identifier des Blocks und dann
können wir für eine Kante UV gucken, ob U und V zum selben Identifier
führen oder zu verschiedenen.
Wenn sie zu verschiedenen führen, liegen sie in verschiedenen
Teilbäumen.
Dann können wir die Kante, die sie verbindet, hinzunehmen und Union
machen.
Und dann haben wir sozusagen einen Teilbaum draus gemacht.
Und deshalb ist diese Union-Find-Datenstruktur genau das, was wir
brauchen, um diesen schon gefundenen Teilwald zusammenzuwachsen zu
lassen zu einem Minimal Spanning Tree.
Wie machen wir das?
Die Idee ist, dass wir verzeigern das und die Elternrelation
repräsentiert die Partition.
Das heißt, wir fangen vielleicht damit an, dass am Anfang jeder nur
auf sich selbst zeigt.
Und später, wenn wir Join gemacht haben, gehört dieses hier zu diesem
Block dazu.
Und wir gehen in eine Richtung und finden dann den eindeutigen
Identifier.
Das heißt, die, die auf sich selber zeigen, repräsentieren die
eindeutigen Namen ihrer Blöcke.
Die, die im Block drinnen sind, die hängen irgendwie drunter.
Und wenn wir jetzt sozusagen parent, parent, parent, parent machen,
bis das Ding auf sich selber zeigt, dann haben wir den eindeutigen
Namen gefunden.
Das heißt, jedes Element, dessen Pointer auf sich selber zeigt,
repräsentiert einen Namen eines Blocks.
Und die anderen, die im Block drinnen sind, zeigen auf andere, die im
Block drinnen sind, bis einer auf den zeigt, der den Block
repräsentiert und die Operation vereint.
Es wird deshalb einfach sein, wir werden gucken, wie der parent-Knoten
heißt, bis der parent-Knoten auf sich selber zeigt.
Wenn der parent-Knoten auf sich selber zeigt, geben wir das als
eindeutigen Namen zurück.
So, das heißt, wir haben find, wir können link machen, wenn i und j
Representatives von verschiedenen Blöcken sind, also i zeigt auf sich
selber, j zeigt sich auf sich selber und darunter hängen sozusagen die
anderen Knoten, die in diesem Block drinnen sind, dann können wir
einfach i auf j zeigen lassen.
Und dann haben wir daraus einen Block gemacht mit dem eindeutigen
Namen j.
Weil wir jetzt, wenn wir find machen würden, hier drüben, würden wir
zu i kommen, i zeigt nicht mehr auf sich selber, i zeigt auf j, j
zeigt auf sich selber, find würde den eindeutigen Namen j zurückgeben.
Aber wir mussten annehmen, dass i und j Representatives von
verschiedenen Blöcken sind für diese Prozedur.
Und Union macht jetzt einfach Folgendes, falls i und j in
unterschiedlichen Blöcken liegen, find von i findet einen anderen
eindeutigen Blocknamen als find von j, dann verlinken wir find von i
und find von j, denn beides sind Repräsentanten ihres Blocks.
Und dann haben wir tatsächlich genau das hier gemacht, wir haben aus
den zwei Blöcken, die verschieden waren, einen Block gemacht.
So, das ist unsere erste Version der Union-Find-Datenstruktur.
Toll ist, Union braucht konstante Zeit, find, also link braucht
konstante Zeit, weil hier muss man zweimal find durchführen und find
braucht Zeit, Theta von n im schlechtesten Fall, das ist uns zu
langsam.
Also im schlimmsten Fall hängen die zugehörigen Knoten wie die Perlen
auf einer Schnur und wir brauchen Blockgröße lange, um herauszufinden,
welches der eindeutige Name dieses Blocks ist.
Das ist uns zu langsam und wir haben die Idee, wir könnten ja die
Pfade kurz halten.
Das heißt, so etwas vermeiden, wo man sehr, sehr lange hangeln muss,
bis man beim eindeutigen Namen des Blocks angekommen ist.
Dafür macht man Pfadkompression.
Die Funktion find wird ein bisschen angepasst, und zwar, wenn parent
von ii ist, dann geben wir das zurück, das ist der eindeutige Name des
Identifiers.
Sonst setzen wir i' als find von parent von i und parent von i setzen
wir danach auf i' fest.
Das heißt, wenn wir für diesen Knoten hier irgendwann einmal den
langen Weg nach oben durchgegangen sind, würden wir danach als
Abkürzung ihn direkt nach oben verlagern.
Und genauso die auf dem Weg, weil wir parent ja hier...
Das heißt, wenn wir den langen Weg einmal gegangen sind, setzen wir
eine Abkürzung und sind in Zukunft sozusagen in einem Sprung da.
Das ist eine Maßnahme der Pfadkompression, die wir machen, dass wenn
wir mühselig mal find gemacht haben, wir danach Abkürzungen setzen.
Das andere ist Union by Rank, bedeutet, wir hängen nicht den tieferen
Baum unter den kleineren, um dadurch einen sehr langen Pfad zu
generieren, sondern wir hängen den kleineren an den längeren, sodass
wir sozusagen, wenn sie unterschiedlich lang sind, bleibt die maximale
Pfadlänge erhalten dadurch.
Und die Pfadlänge wächst dadurch nur logarithmisch, weil wir sozusagen
immer verzweigen und nicht alles untereinander hängen.
Das heißt, Union by Rank macht folgendes, wir merken uns zusätzlich
den Rank, was sozusagen die maximale Tiefe des Baumes ist, von der
Darstellung unseres Blockes.
Und die Procedure Link macht jetzt folgendes, i und j sind wieder die
Repräsentativen, also die Vertreter von unterschiedlichen Blöcken.
Und falls jetzt Rank i echt kleiner ist als Rank j, dann ist Parent
von i j.
Das heißt, wir hängen den kleineren Baum an den schon größeren dran.
Das heißt, wir haben jetzt all die kürzeren Pfade um einen länger
gemacht, aber der längste Pfad hat seine Länge nicht verändert.
Falls Rank i und Rank j gleich ist, dann ist es egal, wen wir an
welchen dranhängen.
Aber wenn wir jetzt hier zum Beispiel sagen, Parent von j ist jetzt i,
dann müssen wir aber den Rank um einen erhöhen.
Jetzt haben wir nämlich zwei gleich tiefe Bäume per Link verbunden und
dadurch ist ein längerer Pfad entstanden, als wir bisher hatten.
Also der Rank von i, der jetzt der neue Repräsentative...
Also wir haben sie so aneinander gehängt, die sind gleich lang, so
aneinander gehängt, dass i der neue Vertreter ist.
Und jetzt ist der Weg von hier nach oben hat jetzt beispielsweise
Länge 3, wenn es vorher Länge 2 war, weil wir diesen zusätzlichen
Schritt gehen.
Deshalb müssen wir sagen, i ist jetzt der eindeutige Name des Blocks,
aber der Rank des Blocks ist um eines größer geworden, weil wir jetzt
um dieses Stück länger die Pfade hier haben.
Wenn sie ungleich tief sind, verbinden wir es so, dass die maximale
Tiefe gleich bleibt.
Damit hat sich der Rank des Baumes nicht geändert.
Wenn sie gleich tief sind, gibt es hinterher einen längeren Pfad, wir
müssen den Rank um einen erhöhen.
So, die Analyse, wir haben diese erste Version schon analysiert, jetzt
gucken wir mal die pfiffigere Version an.
Und zwar bisher mal nur Union by Rank, also dieses mit den
Abkürzungen, die Pfadkompression betrachten wir noch nicht, sondern
nur dieses Union by Rank.
Die Invariante ist, der Pfad zum Vertreter x hat Länge höchstens Rank
von x.
Das heißt, egal wo man in dem Baum ist, höchstens Rank häufig muss man
sich nach oben durchfragen.
Das war ja genau auf die Tiefe des Baumes, Rank.
x ist der Vertreter des Blocks, dann hat die Mengegröße mindestens
zwei hoch Rank x.
Das heißt, es ist tatsächlich der Rank logarithmisch.
Ja, als Korollar, find braucht Zeit, die jetzt nur noch logarithmisch
ist.
Und wenn wir die Bäume so aufbauen, dann haben wir schlimmstenfalls
logarithmische Tiefe.
Und es kann noch besser werden, wenn man sozusagen auch noch immer,
wenn man das Find einmal gemacht hat, diese Abkürzungen fest
verdrahtet.
So, nur Pfadkompression, find braucht Zeit, O von Log n.
Jetzt sagen Sie, haha, so ein Quatsch, ich mache doch find das erste
Mal, da kennt noch niemand die Abkürzung.
Das heißt, es dauert so lange, wie es dauert.
Ja, amortisiert.
Das heißt, wenn Sie es häufig genug machen, geht das sozusagen gegen O
von Log n.
Und den Beweis betrachten wir hier nicht.
So, und jetzt verbinden wir Pfadkompression mit Union by Rank.
Und jetzt passiert was total Erstaunliches, die, obwohl der
Algorithmus relativ einfach ist, wir geschicktes Verbinden der
Teilbäume, so dass die maximale Tiefe möglichst wenig wächst und
dieses Festvertraten der Abkürzungen, beides relativ einfache Ideen,
aber die Analyse auf einmal ist total abgefahren.
Insbesondere kommt eine Funktion vor, die die sogenannte inverse
Ackermann -Funktion ist.
So, und dazu eine kleine Nebengeschichte.
Sie kennen wahrscheinlich Vorschleifen, also vor i gleich 1 bis n, du,
irgendwas.
Und jetzt ist es so, dass man Vorschleifen schachteln kann und kann
dadurch Funktionen programmieren, die ganz schön schnelles Wachstum
haben.
Und je mehr man Vorschleifen schachtelt, umso höheres Wachstum kann
man hin programmieren.
Und noch David Hilbert dachte, dass geschachtelte Vorschleifen die
gesamte Berechenbarkeit sind.
Das heißt, jede Funktion, die man überhaupt berechnen kann, kann man
durch geschachtelte Vorschleifen ausrechnen.
Und dann ein Schüler von David Hilbert, besagter Herr Ackermann, hat
sich eine Funktion ausgedacht, die total abgefahren ist.
Und zwar hat er sich eine Funktion ausgedacht, die so rekursiv
definiert ist, die im Wesentlichen Folgendes macht.
Wenn man das lange anstarrt, sieht man es auch, aber ich versuche es
mal anschaulicher.
Die hat sozusagen zwei Variablen und die eine Variable gibt quasi an,
wie viele geschachtelte Vorschleifen ich habe.
Und die andere gibt dann an Parameter, was man dann mit der Funktion
macht.
Der erste Parameter hilft uns, eine Funktion zu definieren über die
Anzahl der geschachtelten Vorschleifen.
Und der zweite Parameter sagt uns dann, wo wir die auswerten.
Das ist so ein bisschen die Anschauung, die der Ackermann dahinter
hatte.
Das heißt, wenn es stimmen würde, was Hilbert noch dachte, dass
geschachtelte Vorschleifen die gesamte Berechenbarkeit sind, dann
würde jede Funktion, die wir ausrechnen können, eine bestimmte
konstante Anzahl von Schachtelungen haben.
Zum Beispiel 100.000.
Jetzt ist es aber so, diese Funktion, die Ackermann-Funktion, geht
schneller durch die Decke als jede feste geschachtelte Vorschleifen
-Konstruktion, weil ich ja, angenommen, ich könnte die mit 70
geschachtelten Vorschleifen realisieren, dann würde ich einfach den
Parameter, der die Anzahl der Schachtelungen reguliert, auf 170
drehen.
Und dann würde ich auf einmal sehen, die geht durch die Decke viel
schneller als alles, was ich mit 70 geschachtelten Vorschleifen
hinschreiben kann.
In die geschachtelten Vorschleifen nannte man damals natürlich nicht
geschachtelte Vorschleifen, sondern man nannte das eine primitive
Rekursion.
Also die primitiv-rekursiven Funktionen sind nicht alle berechenbaren
Funktionen.
Ein Gegenbeispiel ist die Ackermann-Funktion, die ausnutzt, wie man
primitiv -rekursive Funktionen konstruiert, nämlich im Wesentlichen
über geschachtelte Vorschleifen, und schneller wächst als jede
geschachtelte Vorschleife sich das vorstellen kann.
Und deshalb konnte man damit beweisen, dass es eine berechenbare
Funktion gibt mit einer klaren Berechnungsvorschrift, die aber auf
keinen Fall primitiv-rekursiv sein kann.
Und jetzt ist es so, die Ackermann-Funktion wächst rapide.
Also es genügen zwei Vorschleifen um exponentielles Wachstum
hinzukriegen, und wir finden exponentielles Wachstum schon enorm.
Aber die Ackermann-Funktion wächst schneller als alles, was ich mit
geschachtelten Vorschleifen überhaupt hinkriege.
Das heißt, die hat ein sehr, sehr rasantes Wachstum, und die inverse
Ackermann -Funktion ist deshalb...
Ich will nicht behaupten, es ist eine Konstante, weil das nämlich
ziemlich falsch wäre, aber für alle physikalisch denkbaren Werte ist
die irgendwie kleiner als 5.
Das heißt, diese Analyse hier oben,
M mal Find plus N mal Link brauchen Zeit, O von M mal inverse
Ackermann -Funktion von M, N, bedeutet, letztlich dominiert das M die
Laufzeit, weil asymptotisch diese inverse Ackermann-Funktion im
Wesentlichen kleiner als 5 ist.
Das
Interessante ist, die Ackermann-Funktion ist nicht primitiv-rekursiv,
weil sie schneller durch die Decke geht als jede primitiv-rekursive
Funktion.
Eine primitiv-rekursive Funktion kann ich als geschachtelte
Vorschleifen -Konstruktion endlicher konstanter Tiefe angeben.
Die Ackermann-Funktion überwindet jede dieser Grenzen, weil sie
sozusagen im ersten Parameter festlegt, wie viele Schachtelungen sie
haben will und danach geht sie durch die Decke.
Die inverse Ackermann-Funktion ist primitiv-rekursiv.
Die inverse Ackermann-Funktion ist tatsächlich sehr, sehr langsam
wachsend.
Und ich kann relativ leicht einsehen, dass die inverse Ackermann
-Funktion, da kann ich sozusagen mit einer Vorschleife nachprüfen, ob
das stimmt, weil ich sozusagen so eine riesige Eingabe kriege und so
eine kleine Ausgabe ausgeben soll, dass mir das sozusagen genug gibt,
um mit einer Vorschleife auszukommen.
Das heißt, das muss man sich mal überlegen, das ist ganz lustig, das
Argument, warum die Ackermann-Funktion nicht primitiv-rekursiv ist,
ist über ihr immenses Wachstum.
Und tatsächlich ist es so, dass die inverse Ackermann-Funktion
primitiv -rekursiv ist.
Und jetzt ist es sogar so, dass Hilbert fast recht gehabt hätte.
Und zwar lässt sich jede berechenbare Funktion überhaupt als A
angewendet auf B hoch minus 1 angewendet auf C, wobei A, B und C
primitiv -rekursiv sind.
Das heißt, wir müssen nur eine rumdrehen und dann haben wir dieses
Problem, dass es irrsinnig schnell wachsende Funktionen gibt, die
trotzdem berechenbar sind, im Griff.
Weil gerade diese, die so irrsinnig wachsen, deren inverse ist sehr,
sehr langsam wachsend.
Das heißt, man kann das Argument irgendwie lustig rumdrehen und A nach
B hoch minus 1 nach C für A, B, C primitiv-rekursiv gibt uns alle
Berechenbarkeit.
Und ich nehme an, dass Ihnen das im Rest Ihres Studiums niemand mehr
erzählen wird, weil ich glaube, wenig Leute sich heute damit
beschäftigen.
Aber wenn man schon bei der Ackermann-Funktion vorbeikommt, ist das
sozusagen ein netter Seitenweg.
So, die Ackermann-Funktion wird hier am Beispiel mal demonstriert, wie
rapide die wächst.
Und die wächst so rapide, dass man ab schon relativ kleinen
Parametern, man sich eine neue Notation ausdenken müsste, um überhaupt
mit ihrem Wachstum zurechtzukommen.
Weil die normale Exponentiation-Notation auch wieder nur relativ
schwaches Wachstum hinlegen kann, jedenfalls nicht so rapide wie die
Ackermann -Funktion.
Und wenn Sie jetzt, ich weiß nicht, in der Wikipedia nachgucken nach
großen Zahlen oder sowas, dann finden Sie da vielleicht die Turm
-Notation oder irgend sowas, die eine Verallgemeinerung der
Exponentiation -Operation ist.
Aber die Ackermann-Funktion, wie gesagt, um deren Wachstum zu
beschreiben, hier unten, bräuchten wir eine in der Mathematik sonst
unübliche Schreibweise, weil Exponentiation einfach nicht reicht.
So, jetzt wollen wir den Kruskal-Algorithmus mit Union Find machen,
was im Prinzip nur heißt, wir machen diese Idee mit dem, wenn U und V
verschiedene Teilbäume verbindet, nehmen wir es zum Minimal Spanning
Tree hinzu, sonst lassen wir es weg.
Und das machen wir wie folgt.
Wir betrachten alle Kanten in sortierter Reihenfolge, das heißt, wir
müssen hier sortieren.
Falls in unserer Union Find Datenstruktur Find von U ungleich Find von
V, ja dann liegt es bisher zumindest noch in verschiedenen Teilbäumen,
dann Output UV, denn UV wird jetzt zu unserem Minimal Spanning Tree
dazugehören, wir geben diese Kante einfach mal aus.
Und außerdem machen wir hier ein Union von UV, das heißt, wir
verbinden die beiden Teilbäume zu einem Baum.
Wenn man nur an Korrektheit interessiert ist, genügt hier ein Link,
weil wir ja nicht klar sind, ob U und V die Repräsentanten sind.
Wenn es nämlich keine Repräsentanten sind, dann genügt da kein Link.
Deshalb hier bitte ein Union verwenden.
Die Zeit ist O von M log M, allein schon durch das Sortieren.
Und die
Graph -Repräsentation dafür genügt es, den Graphen als Kantenliste zu
haben.
Wir müssen es sortieren können, damit wir die sortiert durchgehen
können, aber tatsächlich die Graph-Repräsentation, da gibt es keine
großen Ansprüche, sondern es genügt eine Kantenliste zu haben.
Und die Bäume im Minimal Spanning Forest, den wir schon gefunden
haben, entsprechen den Blöcken der Partition.
Deshalb entsprechen diese Blöcke den schon gefundenen Teilbäumen.
Und dann ergibt sich, dass der Kruskal-Algorithmus so aussieht, wenn
wir die Union-Find-Datenstruktur verwenden.
Gut, ein Beispiel.
Am Anfang, man sieht es gar nicht, sind 1, 2, 3, 4 die Knoten.
Jeder ist mit sich selber verlinkt, weil jeder sein eigener bisher
gefundener Spannbaum ist.
Dann gehen wir in sortierter Reihenfolge durch die Kanten, sortiert
nach den Kosten.
Die leichteste Kante ist die Zweierkante.
Und jetzt sehen wir, dass die Zweierkante zwei noch nicht verbundene
Teilbäume verbindet.
Dann machen wir hier einen Link.
Und jetzt ist es so, dass 2 unter 4 hängt.
Das heißt, find von 2 wäre jetzt 4.
Tatsächlich sehen wir in dieser Datenstruktur, dass die beiden hier
zusammengehören.
Die nächste Kante vom Gewicht her ist 3.
Die verbindet tatsächlich zwei bisher nicht verbundene Teilbäume und
deshalb verlinken wir 3 mit 1.
Und 1 ist mit sich selber verlinkt, weil es ein Repräsentant ist.
Dann vom Gewicht her der Nächste ist die 4.
Die 4 verbindet tatsächlich zwei bisher noch nicht verbundene Bäume.
Das heißt, wir verlinken
jetzt die beiden Teilbäume.
Das bedeutet, der eine Repräsentant ist die 1, der andere Repräsentant
war die 4.
Das heißt, jetzt hängen wir die 1 unter die 4.
Das heißt, die 4 ist jetzt der Repräsentant auch für das, was bisher
unter der 1 hing.
Damit haben wir einen Spannbaum gefunden.
Wenn wir jetzt komprimieren wollen, dann würden wir diese Abkürzungen
hier fest verdrahten und würden alles sozusagen direkt unter die 4
hängen.
Wir haben zwei Algorithmen kennengelernt.
Wenn wir die jetzt vergleichen, dann spricht für den Janik-Priem
-Algorithmus, dass er asymptotisch gut ist für alle M&N.
Und er ist sehr schnell, wenn es viele Kanten im Vergleich zu den
Knoten gibt.
Für Kurzgall spricht er es gut, wenn die Menge der Kanten und die
Menge der Knoten etwa gleich sind.
Er ist sehr anspruchslos an die Darstellung des Graphen.
Er braucht eigentlich nur eine Kantenliste, die er dann nach den
Kosten sortiert und einfach durchgeht.
Er profitiert von schnellen Sortierern.
Das heißt, das Sortieren ist dort einer der wesentlichen aufwändigen
Schritte.
Wenn wir das parallelisieren können oder ganzzahliges Sortieren machen
können, weil wir wissen, dass die Kosten aus einem kleinen Bereich
kommen und können da so eine Art Bucket Sort machen, dann wird das
sehr viel schneller.
Mehr darüber wäre, dass wir O von M log N hinkriegen.
Von 1926 ist das, finde ich sehr erstaunlich.
Dann gibt es von 1995 einen Fortschritt, der eine erwartete Zeit von O
von M hat, parallelisierbar ist und externalisierbar.
Externalisierbar bedeutet, dass wir gut zurechtkommen mit externen
Speichermedien, die eventuell langsamer sind.
Und deterministische Zeit, das haben wir schon gesehen.
Es gibt einen optimalen deterministischen Algorithmus und in Karlsruhe
wurde ein praktikabler externer Algorithmus gefunden.
Das betont wieder, was ich bestimmt schon fünfmal erzählt habe, dass
die Algorithmenentwicklung in Karlsruhe sich nicht vorrangig um diese
asymptotischen Werte kümmert, die zum Beispiel für Turing-Maschinen
relevant sind, sondern man betrachtet realistischere Maschinenmodelle,
wo beispielsweise der Cache mit betrachtet wird oder eine
Speicherhierarchie.
Und dann auf einmal macht es einen Riesenunterschied, ob man
Teilprobleme so zurechtschneidet, dass sie in den Cache passen oder
nicht.
Und auf einmal kann man erkennen, welche Algorithmen in Praxis
wirklich schneller sind.
Und die Idee der Forschung ist, dass wenn man merkt, dass man einen
als optimal bewiesenen Algorithmus hat, der in Praxis gar nicht so gut
läuft, dann merkt man, dass man vielleicht sein Rechnermodell mal
wieder anpassen muss an das, was sich so in der Rechnerwelt getan hat.
Und deshalb ist dieser Algorithmus jetzt hier nicht mit irgendeinem
besonders tollen O bezeichnet, sondern als praktikabler externer
Algorithmus, weil der eben für dieses Maschinenmodell, wo man einen
Sekundärspeicher hat, besonders gut ist.
Dann wurde auch KUSCAL verbessert, weniger Sortieraufwand, besser
parallelisierbar.
Und zusammenfassend für das Ganze, was wir über minimale Spannenbäume
gehört haben, ist, wir haben die Schnitteigenschaft und wir haben die
Kreiseigenschaft.
Das sind eine Basis für die abstrakten Algorithmen.
Das heißt, man benutzt abstrakte Problemeigenschaften.
Wir haben auch gesehen, dass die Algorithmen, die wir uns dann
überlegt haben, erst mal sehr abstrakt beschrieben waren.
Wir haben da noch nicht im Detail gesehen, welche Datenstruktur,
Priority Queues oder Union Find Datenstrukturen hier jetzt die
richtigen sind, sondern man hat erst mal das Problem selber betrachtet
und hat Eigenschaften von minimalen Spannenbäumen gefunden,
mathematische Eigenschaften von minimalen Spannenbäumen, aus denen
heraus man dann gesehen hat, wie man prinzipiell minimale Spannenbäume
konstruieren kann.
Wir haben Beweise geführt mittels Austauschargumenten.
Das heißt, wenn man diese oder jene Kante nimmt, hat man immer noch
einen minimalen Spannenbaum und konnte dann hier diese Eigenschaften
beweisen.
Und ganz wichtig, Implementierungen brauchen effiziente
Datenstrukturen.
Das ist auch ein Entwurfsprinzip.
Das heißt, wenn man mal so einen abstrakten Algorithmus gefunden hat,
dann guckt man sich mal, was braucht man da eigentlich?
Muss man zum Beispiel schon gefundene Teilbäume zu Bäumen
zusammenbringen?
Wie würde man das machen?
Und dann kommt man darauf, dass man hier beispielsweise mit der Union
Find Datenstruktur viel schneller ist, als wenn man alles sehr, sehr
naiv macht.
So, dieser Janik-Priem-Algorithmus ist in etwa wie der Dijkstra.
Und das gibt uns noch ein Entwurfsprinzip.
Ein Greedy-Algorithmus, wo man sozusagen immer die bestmögliche
Möglichkeit nimmt, die noch in Betracht kommt.
Die kann man gut implementieren mit einer Priority Queue, weil man da
immer ganz oben den Kandidaten hat, der als nächstes in Frage kommt.
Das heißt, Greedy nimmt sich immer den Delete-Min-Kandidaten, guckt,
ob es den jetzt brauchen kann.
Wenn nicht, nicht.
Wenn ja, war das die bestmögliche Wahl.
Und mit Priority Queues sind Greedy-Algorithmen eben relativ schnell
implementiert.
Und wir haben Union Find kennengelernt, eine effiziente Verwaltung von
Partitionen, wobei richtig effizient es erst wird, wenn man
Pfadkompression macht, also diese Abkürzungen fest verdrahtet.
Und Union By Rank, das heißt, die Bäume richtig herum zusammenhängt,
damit sich, wenn die Bäume ungleich tief sind, die maximale Tiefe
nicht ändert.
Und das war ein Beispiel für einen einfachen Algorithmus, relativ
simple Idee, mit einer äußerst nicht trivialen Analyse.
Sonst wäre die inverse Ackermann-Funktion dort, glaube ich, auch gar
nicht aufgetreten.
Und in diesem Sinne wünsche ich Ihnen einen schönen Tag noch.