Video 11-11: Minimale Spannbäume

0:02 Im nächsten Abschnitt schauen wir uns minimale Spannbäume an. Und dazu erstmal einfaches Beispiel. Äh eine Möglichkeit, wo das zum Einsatz kommen könnte, ist, wenn Sie irgendwie einen Versorgungsnetz planen müssen. Sie haben irgendwelche Häuser, die an bestimmten Stellen stehen. Und was hier an Strecken eingezeichnet ist, an Kanten, das sind mögliche Verbindungen, die man bauen könnte. Äh, ich habe sie mit Stromnetzen angegeben, weil da klar ist, uns interessiert eigentlich nicht unbedingt, ob ich über den kürzesten Weg angebunden bin oder sowas, wie das bei einem Straßennetz vielleicht wichtig wäre. Wir wollen einfach die äh Anzahl Stromtrassen minimieren, denn das kostet ja alles. Äh diese Kanten haben jetzt auch noch ein Gewicht, was angeht, wie teuer es ist, diese Kante zu bauen. Und ähm natürlich abstrahieren wir von dem konkreten Szenario. Das ist einfach irgendein Graf, nur dass er jetzt zusätzlich noch Gewichte hat. In diesem Kapitel sind die Grafen ungerichtet. Für Spannbäume machen ungerichtete Grafen nur Sinn. Und dann wäre hier eine mögliche Lösung, z.B. diese Verbindung, damit ist jedes von den Häusern ans Netzwerk angeschlossen und ähm das ist auch noch eine Lösung, in der die Summe dieser Kosten minimal ist.

1:19 Äh, man kann sich an der Stelle vielleicht sogar schon direkt überlegen. Äh, es hilft nie, wenn ich irgendwo noch so eine zusätzliche Kante einziehe, wenn die einen Kreis schließt, dann waren alle beteiligten Häuser auch vorher schon am Netz oder sind sie jetzt immer noch nicht? Das heißt, das wird immer ein Baum sein, deswegen der Name Spannbaum.

1:49 etwas formaler ähm ist die Eingabe ein ungerichteter Graf, aber kanten gewichtet und äh wir nehmen an, der ist einfach für das Problem ist es so, wenn Sie parallele Kanten haben, dann lassen sie einfach alle wegfallen, außer die günstigste, die würden wir eh nie benutzen. Und wenn es äh Self Loops gibt, die würde man auch nie benutzen, weil es geht ja nur darum, alles zu verbinden. Das heißt, das ist hier keine spannende Einschränkung.

2:13 Wir nehmen aber an, dass der Graf zusammenhängend ist, damit es überhaupt irgendeine Art irgendeine Option gibt, alle zu verbinden. Äh, wenn das nicht der Fall ist, könnte man natürlich immer noch die Komponenten verbinden, aber dann wenden Sie halt diesen Algorithmus auf jeder Komponente an. Äh, noch formaler ausgedrückt, wie man Grafen und Kanten als Mengen modelliert, hatten wir schon besprochen, nur zur Erinnerung. Äh was Neues sind die Kosten und im Allgemeinen, aus theoretischer Sicht ist das eine Abbildung der Kanten in die reellen Zahlen und erstmal ohne weitere Einschränkung werden wir in aller Regel dann weiter einschränken. Ähm auch sich jetzt Gedanken machen, wie man reelle Zahlen im Computer darstellt, dann nehmen Sie double. Das reicht für den für den Punkt hier. Ja, wir werden es tatsächlich ähm noch allgemeiner machen. Wir müssen eigentlich die Zahlen immer nur vergleichen und addieren können. Äh können sich überlegen, welche algebraischen Eigenschaften wir dafür brauchen. Ja, und die Bedeutung von diesem ähm zusammenhängend heißt eben, es gibt ein Weg von jedem Knoten zu jedem anderen.

3:15 Wie sieht eine mögliche Lösung aus? Na ja, das ist ein Spannbaum ist auch ein Graf, nämlich über die gleiche Knotenmenge, aber eine kleinere Kantenmenge ähm muss eine Teilmenge der ursprünglichen Kanten sein. Wir wollen die Kosten minimieren. Kosten ist definiert als die Summe aller Kantenkosten. Und wir wollen, dass der dieser Graf vt zusammenhängend ist und azyklisch ist, also keine Kreise enthält. Wie gesagt, das ist ähm in der Regel ohne Beschränkung der Allgemeinheit äh muss man das nicht fordern, wenn die Kantengewichte nicht negativ sind.

4:03 Neben den offensichtlichen Anwendungen hat das Problem viele andere weitere Anwendungen. Ähm auf die will ich gar nicht im Detail äh weiter eingehen. Äh sind nur so ein paar genannt. Also, es hat natürlich was mit Routing in Netzwerken irgendwo zu tun auf auf offensichtliche Weise. Aber es gibt auch noch so ein paar andere Beispiele ähm, die auf den ersten Blick gar nichts mit Verbindungsnetzen und an Netzanschließen und so weiter zu tun haben, die sich aber als dieses minimale Spannbaumproblem reformulieren lassen. Deswegen ist es so wichtig, dass man dieses Problem mal gesehen hat und die die super schnellen einfachen Algorithmen dafür erkennt, um sozusagen erkennen zu können, wenn eine Anwendung in versteckter Weise nach einem Spannbaum fragt. Natürlich auch eine beliebte Klausible Aufgabe nebenbei, aber das nur so am Rande. Wir werden hier um die Beweise, die Argumente ein bisschen zu vereinfachen, diese Annahme treffen, dass die Kantengewichte alle verschieden sind, paarweise verschieden sind. Das ändert an den Algorithmen eigentlich gar nichts. Äh es macht aber die Argumentation einfacher, weil dann die minimalen Spannbäume eindeutig bestimmt sind.

5:15 Ähm, wenn alle Kanten verschieden sind, dann ist auch die für zwei verschiedene äh Spannbäume, wen wir sehen, ähm die Summe der Kanten verschieden. Und das macht das Argument an einigen Stellen einfacher. Wie gesagt, die äh Algorithmen kümmert das nicht.

5:48 Und die sind auch genauso schnell. ist also äh rein eine Bequemlichkeitsannahme, um ein bisschen die Präsentation zu vereinfachen. ähm strukturiert. Also, sie könnten jetzt ein paar Beispiele äh mal durchspielen und dann stellt man relativ schnell fest. Äh um alles anzuschließen, gibt's zwei zwei äh Kernbegriffe, die einem da das die Sprache liefern, um über das Problem zu reden. Das eine ist ein Schnitt in dem Graf. Formal ist ein Schnitt, eine Aufteilung von dem Graf in zwei Teilmengen, nämlich eine Menge S und dann eben die Komplementmenge. Was die Komplementfarbe von Grün? Vielleicht sowas.

6:46 Also die Komplementmenge, das ist ein Schnitt in dem Graf. Formal ist es eine Teilmenge der Knoten, nicht alle und nicht ähm äh nicht keiner. Aber der spannende Teil ist, dass dieser Schnitt und daher auch der Name Kanten durchschneidet. Es gibt jetzt manche Kanten, die einen Endpunkt im einen oder in und im anderen Teil von diesen von diesem Schnitt haben und das sind die Crossing Edgesutch kreuzende Kanten.

7:21 Das sind eben hier diese roten, die da eingezeichnet sind. In einem Spannbaum, um das Problem zu lösen, muss es irgendwie für die Knoten von S zu den Knoten von V ohne S eine Verbindung geben. Also mindestens eine dieser Kanten muss in jedem Spannbaum enthalten sein, sonst spannt er nicht. Also Spannbaum heißt einfach, er spannt den Graf auf. Daher kommt dieser wirklich dieser Name. Es es gibt sozusagen überall eine Strebe, die den Graf irgendwie stabil hält. Weiß nicht, woher die Metapher kommt. Und unter all diesen Kanten äh sagt diese ähm Eigenschaft hier, dieses Lämmer, können wir davon ausgehen, dass die günstigste kreuzende Kante immer in einem in dem Spannbaum enthalten ist. Und das ist genau der Teil, wo der Beweis einfacher wird. Wir können jetzt sagen in dem minimalen Spannbaum, denn der ist ja eindeutig und äh dann macht das diesen diese Formulierung den Beweis einfacher.

8:25 Um zu sehen, warum das der Fall ist, ähm nehmen wir mal an, dass diese günstigste Kante, das ist diese hier im Bild, nicht Teil von dem günstigsten Spannbaum wäre. Also Widerspruchsbeweis. Wie ich eben schon sagte, irgendeine Kante muss diese zwei Teile verbinden. Also gibt's irgendeine andere Kante F, die die zwei diesen Schnitt verbindet. Also hier noch mal der Schnitt waren war das hier, ja, und dann die anderen. Also irgendwie muss es eine Kante geben, die aus dem grünen Schnitt in den Rest führt. Sei das mal F. Die hat also dann höhere Kosten. Dann kann ich aber einen neuen Spannbaum bauen, indem ich diese Kante F entferne und die Kante E stattdessen eintrage. Dann ist es immer noch ein Spannbaum und er hat geringere Kosten Widerspruch. Das ist im wesentlichen alles. Dementsprechend kann ich für jeden Schnitt die günstigste Kante in den Spannbaum aufnehmen und mach damit nie einen Fehler. Das Schöne ist, das kann ich sozusagen unabhängig machen. Ähm, ich kann das äh für alle Schnitte unabhängig machen und habe immer noch einen korrekten minimalen Spannbaum am Ende.

9:30 Und das ist letztlich die Basis aller Algorithmen für minimale Spannbäume. Man könnte dann so einen allgemeinen greedy Algorithmus, einen gierigen Algorithmus formulieren. Das ist ein Beispiel für eine ganze Klasse von Algorithmen. Auch dazu in effizient Algorithmen, dann ein ganzes Kapitel, wann genau das geht und wann nicht. Das ist quasi die kurzsichtige Art, ein Optimierungsproblem zu lösen. Ich will am Ende die Gesamtsumme von diesem Spannbaum minimieren. Ist mir aber egal. Ich gucke jetzt nur auf meinen aktuellen ganz lokalen Vorteil. Ich nehme z.B. hier diesen Schnitt. Ich weiß, am Ende muss ich den irgendwie überbrücken. Dann gibt's hier eine Reihe von ausgehenden Kanten. Jetzt muss ich die alle durchgehen. In der rein in dem Bild hier ist das bisschen bescheiden gemacht, weil ich jetzt immer hier an der Liste gucken muss, aber wir erinnern uns ja, dass das hier die günstigste Kante war. Ähm, könnte man jetzt hier noch mal prüfen. 1 Z ist auch irgendwo. Die sind nicht mal sortiert. Ihr wollt mir das Leben auch recht schwer machen hier. Na gut. Ähm, das heißt, ich kann diese rote Kante in den Spannbaum aufnehmen, ohne mir irgendeinen anderen Schnitt anzugucken.

10:46 Machen wir noch ein ähm einen mit weniger Kanten vielleicht. Äh, also könnt auch sowas nehmen. Die sechs ist abgeschnitten vom Rest. Die muss irgendwie verbunden sein. Also gucke ich mir die ganzen Kanten von sechs weg an. Und Bild nach müsste 62 hoffentlich die günstigste sein. Gibt's noch eine günstigere? 60 63 ist auch irgendwo 36. Genau, das ist die günstigste. Also 62 ist die günstigste Kante hier für diesen blauen Schnitt. Das heißt, auch die kann ich fest in den in den Spannbaum aufnehmen, ohne dass ich wissen musste, welche Eigenscha welche Wahl die grüne Kante die der grüne Schnitt getroffen hat. Und auch hier wieder ist das Leben einfacher, weil die Kanten ähm ein eindeutig minimales Gewicht haben in jedem Teil, weil sie alle verschiedene Gewichte haben, kann ich mir auch nicht bei äh Gleichstand irgendwie mal die eine mal die andere Entscheidung einbrocken. Okay. Äh das findet tatsächlich einen minimalen Spannbaum und im Grunde haben wir auch schon bewiesen, warum.

11:55 ähm denn äh jede Kante, die dieser Algorithmus aufnimmt, muss Teil von dem minimalen Spannbaum sein, von dem minimalen Spannbaum, denn wir haben sie ja genauso gewählt, wie das diese Cut Property, wie das Lemmer sagte. Wir haben ein Schnitt gewählt und die günstigste kreuzende Kante in den Spannbaum aufgenommen. Solange wir ähm noch nicht Bau -1 N-1 Kanten gewählt haben, kann der Graf noch nicht so der der Spannbaum noch nicht spannend sein, kann der der Teil äh Spannbaum noch nicht fertig sein. Dann muss es aber auch in diesem Teil jetzt noch irgendeinen Schnitt geben, der noch nicht verbunden ist. Dementsprechend gibt's für diesen Schnitt wieder eine günstigste kreuzende Kante. Die nehme ich mit auf und ich mache einen Schritt weiter. Das heißt, ich kann nur terminieren, wenn es keinen Schnitt mehr gibt ohne kreuzende Kante. Und äh dann bin ich genau in diesem ersten Fall. Also ich ich wähle nie eine falsche Kante und ich höre nie auf Kanten zu wählen, bevor ich fertig bin.

12:55 Das ist das Korrektheitsargument. Und dementsprechend ist jede Möglichkeit, diesen Algorithmus zu implementieren korrekt. Was wir jetzt nicht besprochen haben, ist wie man das im Detail macht, denn ich hatte jetzt einfach nur gesagt, wähle eine Teilmenge der Knoten und finde die günstigste kreuzende Kante. Es gibt exponentiell viele Teilemen, das ist schon mal ein Problem und ich müsste auch effizient diese Kanten finden. Äh, es gibt verschiedene Möglichkeiten, das zu tun. Wir werden uns hier aber nur die einfachste erste anschauen. Ähm wie gesagt, wenn Sie mehr sehen wollen, müssen Sie noch für die effiziente Algorithmen zurückkommen. Ähm die einfachste Variante schauen wir uns hier an. Das ist Crusk Algorithmus, der genau diese Fragen beantworten muss. Welchen Cut wählen wir und wie finden wir diese günstigste kreuzende Kante?

13:54 Fragen an der Stelle erstmal soweit der abstrakte Algorithmus. Okay, jetzt tauchen wir noch ein bisschen noch in die Implementierung ein. Erstens haben wir eine neue Art von Graf. Wir brauchen nämlich jetzt Gewichte auf den Kanten und an der Stelle ist die bequeme Wahl hier vielleicht zu sagen, wir machen nicht mehr diese Kanten ähm Adiazliste wie bisher, in denen es keine echten Kantenobjekte gab und die Adjazlisten nur den Zielknoten speichern, sondern wir machen jetzt Kanten sind First Class Citizens haben ihr eigenes Objekt, das heißt es gibt ein Objekt Kante ähm und die haben einen Start und Endpunkt und ein Gewicht. In dem Fall hier ist es natürlich eine ungerichtete Kante. Das heißt, das der Start und Endpunkt, die sind für uns äh gleich bedeutend. Und eine ganz hübsche ähm Implementierung dafür ist zu sagen, ich kann diese Kante fragen, gib mir einen deiner Endpunkte und wenn ich einen der Endpunkte habe, dann kann ich sie fragen und welches ist der andere?

14:52 Das macht den Code recht kompakt. Sie hätte natürlich auch sagen können, die Kante hat einen ersten und ein zweiten Knoten, aber auf die Weise ist so ein bisschen mehr gezwungen, gar nicht drauf zu gucken, in welche Richtung, welcher dieser Knoten zuerst ähm übergeben wurde im Konstruktor.

15:08 Okay. Ähm, die Kante hat auch ein Gewicht und dieses Compare to vergleicht Kanten bezüglich dieses Gewichts mit dem Kantenobjekt. Das ist natürlich kein besonders schwierige das eine reine Datenklasse. Das heißt, ich habe die Daten, die ich speichern muss, die initialisiere ich im Konstruktor. Äh in dieser Methode gebe ich einfach ohne Beschränkung der Allgemein diesen ersten Knoten zurück. Weiß ja niemand. Äh mit prüfe ich, welchen ich bekommen habe und gebe jeweils den anderen zurück. Und compare zu Vergleich das Gewicht, wie eben gesagt, das sind alles sozusagen all diese Bausteine haben sie in verschiedener Variationen irgendwo am Anfang schon gesehen. Deswegen springe ich da jetzt mal relativ zügig drüber. Was noch fehlt, ist dann der Graf. Also jetzt ein kantengewichteter ungerichteter Graf.

16:00 Ähm, sieht ansonsten quasi genauso aus wie die ungewichtete Variante. Einziger Unterschied, wenn ich eine Kante hinzufügen will, dann übergebe ich jetzt ein Kantenobjekt statt einfach die zwei Knoten wie bisher. Und entsprechend auch die Adiazenzlisten haben jetzt eben Kantenobjekte und nicht mehr nur den den Zielknoten.

16:23 Okay. Äh sieht grafisch dann etwa so aus. Äh, das ist ähnlich, wie wir es bisher hatten. Es gibt auch wieder so ein Format, was das aus einem aus einer Standardin oder aus Text ausliest. Ähm, einziger Unterschied, der vielleicht interessant zu erwähnen ist, diese Kantenobjekte speichern natürlich jetzt immer beide Endpunkte. Also auch in der Adzenliste vom Knoten 0 taucht Knoten 0 hier in jeder Kante noch mal auf und damit muss ich halt dann entsprechend umgehen. Außerdem ist das gleiche Kantenobjekt zweimal vertreten. Das sehen Sie hier für die Vorwärts und Rückwärtsrichtung. Das hatten wir bisher ja auch schon so gemacht. Ähm hier ist aber jetzt sozusagen wichtig, dass oder wir bestehen darauf, dass es wirklich das gleiche Objekt ist.

17:10 Okay, auch das ist einfach zu implementieren. Ähm eigentlich alles genauso wie wie im ungerichteten Fall eben entsprechend angepasst auf die Kanten. Das ist so Kategorie äh kleinstes KI Modell. Mach mal die passenden Änderung. ähm passiert tatsächlich nichts spannendes.

17:35 Damit können wir jetzt unser minimales Spannba definieren. Auch da Sie wissen, jeder Grafalgorithmus wird eine Klasse. So, auch hier im Konstruktor kriege ich den Graf übergeben. Dann macht er sein Ding für den Algorithmus aus, den wir gleich besprechen. Und dann kann ich mir von dieser Klasse ausgeben lassen, welche Kanten sind in dem im Spannbaum. Und so sieht das dann in unserem Beispiel z.B. aus. Äh da würde ich eben dann diese Kanten, die hier schwarz gezeichnet sind, äh ausgegeben bekommen.

18:15 Gehen wir zu der spannenderen Frage. Wie mache ich jetzt diesen Algorithmus, den ich beschrieben habe, als nimm irgendeinen Schnitt und finde die günstigste kreuzende Kante und nimm die und mach mal weiter, bis du fertig bist. Wie machen wir das systematisch? Und ähm Craftskills Algorithmus ist die vielleicht einfachste Idee. Wenn ich eh immer nach günstigsten Kanten suche, dann laufe ich die Kanten in sortierter Reihenfolge durch nach Gewicht. Ich nehme zerst die günstigste Kante. Die erste Kante werde ich immer aufnehmen. Das ist hier äh gemacht nach sortierter ähm in sortierte Reihenfolge der Gewichte. Und ich nehme einfach alle Kanten auf, die ich kann. Und welche kann ich nicht aufnehmen, die die in Kreis schließen. Also ich nehme die ersten fünf Kanten hier auf. 07 2 3 gibt auch gleich noch ein bisschen mehr Animation. 02 57 und an der Stelle käme ich jetzt zu 13. Das heißt, ich würde diese Kante hier prüfen, aber die schließenden Kreis zwischen 1 und 3 sind schon verbunden. Die nehme ich also nicht auf.

19:23 Das ist alles. Ähm, eine Metapher, die Sie da im Kopf behalten könnten, wäre die folgende. Vielleicht hilft's ihnen, vielleicht auch nicht. Wir lassen im Prinzip die Kanten Stück für Stück wachsen. Das ging zu schnell. Noch mal. Ich lasse die Kanten wachsen und sozusagen proportional zu ihrem Gewicht werden die fertig und wenn eine Kante fertig ist, dann wird sie in den Baum aufgenommen, wenn die zwei Endpunkte noch nicht verbunden sind und ansonsten verwerfe ich sie. Also äh andersrum langsam geht nach Speed nach groß.

20:14 Jetzt aber ähm die günstigste Kante war die hier, glaube ich, ne? 1,6. Dann sehen Sie, die werden aufgenommen. Die ersten paar werden immer aufgenommen und dann habe ich hier diese Kante 13. Äh, die wird verworfen, weil 1 und 3 zu dem Zeitpunkt schon verbunden waren. Okay. Ähm, systematischer, wie machen wir das in der tatsächlichen Implementierung? Wir gehen die Kantenliste ein, Kante nach Kante durch. Äh was die Farben hier sind, sind Zusammenhangskomponenten zu diesem Zeitpunkt. Jeder Knoten in seiner eigenen Farbe. Nachdem ich die erste Kante betrachtet habe, 0 und 7 waren noch nicht die gleiche Zusammenhangskomponente, also mache ich sie jetzt zu einer und nehm die Kante auf. Nächste Kante. Z und 3 haben auch verschiedene Farben aufnehmen. 1 und 7 verschiedene Farben aufnehmen. 2 und se 0 und 2 verschiedene Farben aufnehmen. Und sie sehen, dann verschmilzt eben die Farbe dieser ganzen. Okay. Äh können den Rest noch laufen lassen, aber ich denke sie hier habe ich Kanten, wo die Farbe schon gleich ist. An der Stelle nehme ich die dann nicht auf.

21:30 Wie machen wir das aber systematisch? Ich muss ja jetzt irgendwie erkennen, ob ich eine Kante aufnehmen darf oder nicht und bitte möglichst schnell. Eine Option wäre, wir machen jedes Mal eine Tiefensuche von dem einen Knoten und gucken, ob wir den anderen Endknoten erreichen. Das funktioniert.

21:48 Äh, tatsächlich können wir es aber viel viel schneller mit der Union Findatenstruktur von einigen Wochen her. Ja, sie erinnern sich, die hat genau genau was wir hier brauchen implementiert. Ich fange an mit Objekten jedes seiner einzelnen äh Klasse und ich kann Fragen, sind zwei in der gleichen Klasse? und ich kann zwei Klassen vereinigen, indem ich eine Kante einfüge. Das ist letztlich genau, was da auch ähm dahinter steckt. Das heißt, in jedem Schritt von Kruskals Algorithm von Cruskels Algorithmus haben wir eine Kante, für die wir ein Feind Aufruf machen. Sind die zwei Endpunkte in verschiedenen Komponenten aktuell? Wenn ja, dann nimm die Kante auf und mach einmal Union auf den beiden und dann sind sie hinterher in der gleichen Komponente sass dann hier bei so einem Check aus rauskommen würde. Hat schon die gleiche ID, bitte nicht noch mal aufnehmen.

22:47 Das ist genau was wir da ähm brauchen und Union Find liefert das. Und sie erinnern sich, Union Find hatte ähm in der in der ultimativen Version mit Fahkomprimierung und Weited Union ähm diese absurde Laufzeit von iteriertem Logarithmus. Wie oft muss ich den Logarithmus anwenden, um von V auf 1 zu kommen? Das ist das Log, also äh fünf für dieses Universum oder weniger. Im Code lässt sich genau das dann auf Basis von diesen ähm Datenstrukturen, die wir schon gebaut haben, sehr effizient hinschreiben. Ich kann einmal die äh die Kanten eine Priority Queue packen. Ich könnte sie auch vorab sortieren. Das hier hat noch den Vorteil, wenn es ganz ganz viele Kanten gibt, kann ich früher aufhören und muss nicht alle sortieren, sondern ich sortiere mir sozusagen nur, ich lass mir nur die die kleinsten Kanten geben bis dahin, wo ich es brauche. Das weiß ich vorher nicht genau bisin das ist. Ähm, das ist also die binären HEBS, was dahinter steckt, die Min Priority Cues.

23:52 Union Find ist auch eingebaut, können wir also auch direkt wieder verwenden. Und dann laufen wir, solange wir noch Kanten haben oder solange wir noch Kanten für unseren Spannbaum brauchen. Eins von beiden ist zuerst fertig. Das darf eigentlich nicht passieren in dem zusammenhängten Graf, aber wer weiß, was uns der Nutzer gibt. Ähm, ich hole mir die nächste Kante, die mit dem nächst kleineren Gewicht. Guck mir die Endpunkte an. Wenn die schon verbunden sind nach Union Find, dann ignoriere ich die Kante und mach weiter. Äh, falls sie noch nicht verbunden sind, dann mache ich sie jetzt verbunden und nehme sie in die in den in die Lösung mit auf. extrem kompakter Code für einen relativ cleveren Algorithmus am Ende oder sehr effizienten Algorithmus, der aber einfach massiv davon profitiert, dass wir jetzt schon Semester lang vorgearbeitet haben.

24:48 Worst case Laufzeit ergibt sich aus dem Sortieren der Kanten. Also selbst obwohl wir nur n -1 Kanten am Ende brauchen oder e V-1 Kanten in der Notation am Ende brauchen, könnte es passieren in manchen Grafen, dass ich dafür alle Kanten einmal durchprobieren muss. Vielleicht ist erst die letzte Teuerste diejenige, die den letzten Knoten noch in den Baum aufnimmt. Äh kann man sich nicht ohne weiteres drum drücken. Es sei denn, die Kanten sind schon sortiert, dann habe ich eventuell Glück. Äh, der ganze Union Find Teil ist so günstig, dass der asymptotisch gar nicht ins Gewicht fällt. Also das Sortieren der Kanten dominiert die Laufzeit von Cruskells Algorithmus und sortieren ist aber effizient. Das heißt, es ist insgesamt ein sehr sehr einfach lösbares Problem. Minimale Spannbäume sind fast so schnell zu lösen wie den Graf zu lesen.