Minimaler Spannbaum: Prim
Philipp Jenke
https://www.youtube.com/watch?v=P2-hmUfOkvw

Transkript (automatisch erstellt)

0:03 Und auch hier bei den minimalen Spannbäumen wollen wir einen zweiten Algorithmus betrachten. Hier den Algorithmus von Prim. Vorgeschlagen
0:11 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
0:20 einem beliebigen Knoten beginnen und dann schrittweise iterativ Nachbnoten mit minimalem Kantengewicht hinzufügen. Auch das wieder organisiert durch eine
0:30 Warteschlange. Wir schauen uns auch hier wieder den Algorithmus im Pseudocode an. Wir starten damit, dass wir unsere Warteschlange mit allen Knoten
0:37 initialisieren und unsere Ergebnisliste für die Kanten, die in dem minimalen Spannbaum sind, initialisieren wir als ähm eine leere Liste. Dann laufen wir
0:48 ü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
0:58 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
1:07 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
1:16 dann vielleicht hingehen können, um einen weiteren Knoten mit einzubauen. Wir haben eine Schleife über unsere Warteschlange, die läuft so lange, bis
1:23 die Warteschlange leer ist. Wir nehmen das günstigste Element, also das Element mit den geringsten Kosten aus der Warteschlange. Im allerersten Durchlauf
1:31 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
1:40 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
1:49 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
1:56 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
2:04 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
2:15 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
2:26 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
2:38 wir auf das entsprechende Kantengewicht. Das bedeutet also nichts anderes als wir haben jetzt eine Verbindung hier zwischen den beiden. Wir können
2:48 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
2:56 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
3:05 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.
3:16 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
3:25 keine ähm Kante extrahiert. Dann äh aktualisieren wir ähm unsere Warteschlange von A. Wenn wir hier mal gucken, haben wir Kanten nach
3:35 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
3:46 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.
3:55 Alle anderen Knoten haben weiterhin unendliche Kosten. Dann entnehmen wir folglich den Knoten D, weil das der erste ist in unserer Warteschlange und
4:05 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
4:14 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
4:23 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
4:31 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
4:40 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
4:48 Kanten einbauen, jeweils um einen weiteren Knoten anzuknüpfen und haben dann am Ende die blauen Kanten extrahiert, die unseren minimalen
4:59 Spannbaum darstellen. Die Komplexität dieses Algorithmus ähm äh ist abhängig einerseits von der ähm Anzahl der Kanten
5:09 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
5:19 sehr schwer abschätzen, weil je nach Anwendungsfall einer der beiden schneller ist. Es gibt also nicht so eine einfache Handreichung, äh ob man
5:27 eher mit Prim oder mit Kruskall arbeiten soll, äh wenn man aus auf die Performance aus ist. Beide liefern korrekte Ergebnisse und je nach
5:36 Anwendungsfall üben ist einmal der eine Performanter und einmal der andere. M.