12_Algorithmen&Datenstrukturen || minimaler Spannbaum Algorithmen von Kruskal&Prim
Tutorial City
https://www.youtube.com/watch?v=cNooziYBwyw

Transkript (automatisch erstellt)

0:00 [Musik] hallo und herzlich willkommen bei Tutorial City heute geht es um das Thema minimale spannbäume bzw um die
0:14 Algorithmen von Prim und gruskal wir definieren einen minimalen Spannbaum als einen azyyklischen zusammenhängenden teilgraf eines
0:23 ungerichteten Grafen der jedoch alle Knoten des Grafen enthält azyyklisch bedeutet so viiel wie dass der Graf kreisfrei ist stellt sich die Frage wozu
0:32 brauche ich eigentlich einen minimalen Spannbaum minimale spannbäume werden unter anderem gebraucht um Ruten zu berechnen stellen wir uns vor wir haben
0:40 das folgende Straßennetz hier möchte der mülldienst so schnell wie möglich das Altglas aus den öffentlichen Müllcontainern abholen und dazu muss die
0:48 kürzeste Route berechnet werden das kann unter anderem mit der Methode des minimalen spannbaums gelöst werden schauen wir uns das minimale
0:57 spannbaumprblem an einem expliziten Beispiel an indem wir den Algorithmus von Prim und den Algorithmus von kruskal anwenden ziel ist es in diesem Beispiel
1:07 alle Knoten zu verbinden wobei der entstehende Baum zu jedem Zeitpunkt kreisfrei sein muss wie in der Definition vorgegeben die beiden
1:15 Algorithmen von kruskal und Prim sind greedy Algorithmen bei jedem Schritt den ein greedy Algorithmus macht muss er sich zwischen einer von mehreren
1:24 Möglichkeiten entscheiden die greedy Strategie besteht darin immer die beste Möglichkeit zu ne nehmen die in dem Moment die beste zu sein scheint was
1:33 allerdings nicht dafür garantiert dass es die optimale Gesamtlösung ist crusgal löst das Problem in diesem Graf einen minimalen Spannbaum zu finden
1:42 folgendermaßen dieser Algorithmus sucht im gesamten Grafen immer die leichteste Kante und markiert diese das wird so lange gemacht bis alle Knoten verbunden
1:51 sind und zu keinem Zeitpunkt ein Kreis entsteht wir nehmen also zuerst die Kante mit dem Gewicht 1 dann die Kante mit dem Gewicht 2 wobei er sich zwischen
2:00 zwei Kanten mit dem gleichen Gewicht entscheiden kann solange die Definition nicht verletzt wird als nächstes nehmen wir die zweite Kante mit dem
2:08 kantengewicht 2 dann die Kanten mit den Gewichten 4 die Kante mit dem Gewicht 6 kann nicht zum entstehenden teilgraf hinzugefügt
2:16 werden da sonst ein Kreisen stehen würde wir können also auch nicht die Kante mit dem kantengewicht 7 Hinzufügen von Knoten B nach Knoten D es werden solange
2:26 die Kanten zu den teilgrafen hinzugefügt bis alle Noten erreicht wurden kommen wir zum Algorithmus von Prim der ähnlich funktioniert wie der
2:35 Algorithmus von dextra bzw die Breitensuche wie bei der Breitensuche haben wir einen Startknoten in diesem Fall a nun wird von A diejenige
2:44 ausgehende Kante genommen welche das geringste kantengewicht hat also die Kante von A nach C nun werden wieder alle Kanten von dem bisherigen
2:53 bestehenden teilgrafen überprüft und diejenige mit dem geringsten kantengewicht zum teilgrafen hinzugefügt wenn wir zwei Kanten haben die jeweils
3:02 das gleiche minimale kantengewicht haben dann können wir uns wie bei krusgal für eine der beiden Möglichkeiten entscheiden wir fügen in diesem Fall die
3:10 Kante von C nach F hinzu danach ist die minimalste Kante die vom bisherigen teilgrafen gesehen wird die Kante von F nach D mit dem kantengewicht
3:20 2 die Kanten werden so lange hinzugefügt bis ebenfalls alle Knoten entdeckt wurden
3:36 die beiden Algorithmen unterscheiden sich also in einem wichtigen Punkt bei kruscal werden die Kanten mit dem minimalen Gewicht hinzugefügt wobei der
3:44 Graf nicht zusammenhängen muss allerdings bei Prim muss der Graf zu jedem Zeitpunkt Zusammenhängen noch eine kleine
3:52 Anmerkung falls ihr euch die Frage stellt was der Unterschied zwischen dem Algorithmus von Prim und dixtra ist der Algorithmus von dexra findet die
3:59 minimale des von einem bestimmten Knoten zu einem anderen Knoten der Algorithmus von Prim jedoch gibt einen minimalen Spannbaum eines gegebenen Grafen zurück
4:08 er verbindet also alle Knoten wobei die Summe aller Kanten die minimalste ist mit dem Algorithmus von dextra kann man also von jedem beliebigen Knoten zu
4:17 einem anderen beliebigen Knoten mit minimalen Kosten gehen das kann man mit dem Algorithmus von Prim nicht das war's zum Thema minimale spannbäume bzw zu den
4:26 Algorithmen von kruskalum Prim wenn euch das Video gefallen hat dann bewertet es bitte mit einem Daumen nach oben und abonniert den Kanal um kein Video mehr
4:35 zu verpassen bis zum nächsten Video tschüss