Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Minimaler Spannbaum: Prim
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 37 Zeilen
- Und auch hier bei den minimalen Spannbäumen wollen wir einen zweiten Algorithmus betrachten. Hier den Algorithmus von Prim. Vorgeschlagen
- schon 1930, dann später wieder entdeckt entdeckt von Prim und Digra. Deixa hatten wir ja schon bei den kürzesten Pfaden. Die Idee hier ist, dass wir mit
- einem beliebigen Knoten beginnen und dann schrittweise iterativ Nachbnoten mit minimalem Kantengewicht hinzufügen. Auch das wieder organisiert durch eine
- Warteschlange. Wir schauen uns auch hier wieder den Algorithmus im Pseudocode an. Wir starten damit, dass wir unsere Warteschlange mit allen Knoten
- initialisieren und unsere Ergebnisliste für die Kanten, die in dem minimalen Spannbaum sind, initialisieren wir als ähm eine leere Liste. Dann laufen wir
- über alle Knoten und setzen die Kosten für den Knoten auf äh unbegrenzt und der Vorgänger äh dieses Knoten wird auf Nall gesetzt. Vorsicht, Kosten und Vorgänger
- ist hier nicht das gleiche wie bei dem bei der kürzesten Pfadesuche, sondern das sind tatsächlich jeweils nur die Kosten, um den Knoten an unsere
- bestehende Kantenliste anzuschließen. Und der Vorgänger wäre ein Knoten, der schon in der aktuellen Kantenliste drin ist vom minimalen Spannbaum und wo wir
- dann vielleicht hingehen können, um einen weiteren Knoten mit einzubauen. Wir haben eine Schleife über unsere Warteschlange, die läuft so lange, bis
- die Warteschlange leer ist. Wir nehmen das günstigste Element, also das Element mit den geringsten Kosten aus der Warteschlange. Im allerersten Durchlauf
- wird das eins mit Kosten unendlich sein, weil wir die ja bisher noch äh gar nicht gefunden haben. Dann müssen wir einmal eine Sonderbehandlung machen. Ab dem
- zweiten Element funktioniert das alles. Aber ähm genauso ist es mit der ersten Kante, die wir hier entnehmen, indem wir sagen, wir nehmen den Vorgänger von V
- und V. Das heißt, wir haben hier dann irgendwann festgestellt, es gibt eine Kante zwischen diesem Vorgänger von V und V, sonst hätten wir hier den
- Vorgänger nicht gesetzt und das wird als Teil unserer Kantenliste gesetzt. Wie gesagt, Ausnahme für das allererste, wo wir mit einem Zufallselement starten
- wollen. Jetzt laufen wir über die Liste aller Kanten. Alle Kanten in dem Fall mit den Knoten U und V. Jetzt überprüfen wir, ob sich V in Q befindet, also in
- der Warteschlange und ob die Kosten dieser Kante kleiner sind als die Kosten, die aktuell mit V assoziiert sind. Wenn das der Fall ist, ähm dann äh
- setzen wir den Vorgänger von U. Ja, das wäre also hier der zweite Knoten, der in dieser Kante enthalten ist auf V. Und die Kosten von U setzen
- wir auf das entsprechende Kantengewicht. Das bedeutet also nichts anderes als wir haben jetzt eine Verbindung hier zwischen den beiden. Wir können
- U erreichen über V und umgekehrt und deswegen markieren wir die entsprechend. Und das machen wir wie gesagt für alle Kanten in unserem Datensatz und dann in
- der äußeren Schleife, bis wir alle Knoten betrachtet haben und können damit schrittweise unseren minimalen Spannbaum aufbauen. Auch das gucken wir uns wieder
- an in einem äh Beispiel. Äh in unserer Wartestange sind jetzt zunächst mal alle Knoten ähm in enthalten und jeweils mit Kosten unendlich ohne einen Vorgänger.
- Zufällig haben wir jetzt den Knoten A extrahiert. Ja, das ist der erste und wir hatten gesagt, bei der allerersten ähm beim allerersten Durchlauf wird noch
- keine ähm Kante extrahiert. Dann äh aktualisieren wir ähm unsere Warteschlange von A. Wenn wir hier mal gucken, haben wir Kanten nach
- C, D und B. Das heißt, also für ähm diese drei können wir jetzt jeweils Kosten assoziieren. Wir kommen ähm äh nach D mit Kosten 2, der kommt ganz
- vorne in die Warteschlange. Nach B kommen wir mit Kosten 3, der kommt hier als zweites. Und nach C kommen wir mit Kosten 4, der steht an vierter Stelle.
- Alle anderen Knoten haben weiterhin unendliche Kosten. Dann entnehmen wir folglich den Knoten D, weil das der erste ist in unserer Warteschlange und
- wir sind von A nach D gekommen. Das heißt also die Kante AD wird mit in unseren minimalen Spannbaum aufgenommen. D wird hier also entfernt. Ähm dann
- schauen wir uns von D wieder die Nachbarn an. Das wäre C, F, G und so weiter. Das heißt, es aktualisiert sich hier unsere Warteschlange. Wir sehen
- jetzt hier, dass wir tatsächlich alle ähm Knoten, die wir noch nicht betrachtet haben, in der Warteschlange drin haben. Der Knoten, den man mit den
- geringsten Kosten erreichen kann, das ist der Knoten B. Der wird als nächstes extrahiert. Der Vorgänger dafür, also der Knoten zu dem wir mit über den wir
- zu B gekommen sind, mit Hilfe einer Kante war A. Folglich nehmen wir die Kante AB mit auf und dann sehen wir, dass wir schrittweise hier weitere
- Kanten einbauen, jeweils um einen weiteren Knoten anzuknüpfen und haben dann am Ende die blauen Kanten extrahiert, die unseren minimalen
- Spannbaum darstellen. Die Komplexität dieses Algorithmus ähm äh ist abhängig einerseits von der ähm Anzahl der Kanten
- und dann wieder superlinear in der Anzahl der Knoten. Ähm im Allgemeinen lässt sich aber tatsächlich die Performance im Vergleich zu Kruskal sehr
- sehr schwer abschätzen, weil je nach Anwendungsfall einer der beiden schneller ist. Es gibt also nicht so eine einfache Handreichung, äh ob man
- eher mit Prim oder mit Kruskall arbeiten soll, äh wenn man aus auf die Performance aus ist. Beide liefern korrekte Ergebnisse und je nach
- Anwendungsfall üben ist einmal der eine Performanter und einmal der andere. M.
Zum Nachlesen
Algorithmus von PrimDer Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen.
Algorithmus von KruskalDer Algorithmus von Kruskal ist ein Greedy-Algorithmus der Graphentheorie zur Berechnung minimaler Spannbäume von ungerichteten Graphen. Der Graph muss dazu …
Algorithmus von BorůvkaDer Algorithmus von Borůvka gilt als erster Algorithmus zum Auffinden minimaler Spannbäume in ungerichteten Graphen. Er wurde 1926 von dem tschechischen …
Dijkstra-AlgorithmusDer Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy-Algorithmen und löst das Problem der …