Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
12_Algorithmen&Datenstrukturen || minimaler Spannbaum Algorithmen von Kruskal&Prim
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 31 Zeilen
- [Musik] hallo und herzlich willkommen bei Tutorial City heute geht es um das Thema minimale spannbäume bzw um die
- Algorithmen von Prim und gruskal wir definieren einen minimalen Spannbaum als einen azyyklischen zusammenhängenden teilgraf eines
- 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
- brauche ich eigentlich einen minimalen Spannbaum minimale spannbäume werden unter anderem gebraucht um Ruten zu berechnen stellen wir uns vor wir haben
- 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
- kürzeste Route berechnet werden das kann unter anderem mit der Methode des minimalen spannbaums gelöst werden schauen wir uns das minimale
- spannbaumprblem an einem expliziten Beispiel an indem wir den Algorithmus von Prim und den Algorithmus von kruskal anwenden ziel ist es in diesem Beispiel
- alle Knoten zu verbinden wobei der entstehende Baum zu jedem Zeitpunkt kreisfrei sein muss wie in der Definition vorgegeben die beiden
- Algorithmen von kruskal und Prim sind greedy Algorithmen bei jedem Schritt den ein greedy Algorithmus macht muss er sich zwischen einer von mehreren
- 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
- 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
- folgendermaßen dieser Algorithmus sucht im gesamten Grafen immer die leichteste Kante und markiert diese das wird so lange gemacht bis alle Knoten verbunden
- 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
- zwei Kanten mit dem gleichen Gewicht entscheiden kann solange die Definition nicht verletzt wird als nächstes nehmen wir die zweite Kante mit dem
- kantengewicht 2 dann die Kanten mit den Gewichten 4 die Kante mit dem Gewicht 6 kann nicht zum entstehenden teilgraf hinzugefügt
- 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
- die Kanten zu den teilgrafen hinzugefügt bis alle Noten erreicht wurden kommen wir zum Algorithmus von Prim der ähnlich funktioniert wie der
- Algorithmus von dextra bzw die Breitensuche wie bei der Breitensuche haben wir einen Startknoten in diesem Fall a nun wird von A diejenige
- ausgehende Kante genommen welche das geringste kantengewicht hat also die Kante von A nach C nun werden wieder alle Kanten von dem bisherigen
- bestehenden teilgrafen überprüft und diejenige mit dem geringsten kantengewicht zum teilgrafen hinzugefügt wenn wir zwei Kanten haben die jeweils
- 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
- 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
- 2 die Kanten werden so lange hinzugefügt bis ebenfalls alle Knoten entdeckt wurden
- die beiden Algorithmen unterscheiden sich also in einem wichtigen Punkt bei kruscal werden die Kanten mit dem minimalen Gewicht hinzugefügt wobei der
- Graf nicht zusammenhängen muss allerdings bei Prim muss der Graf zu jedem Zeitpunkt Zusammenhängen noch eine kleine
- Anmerkung falls ihr euch die Frage stellt was der Unterschied zwischen dem Algorithmus von Prim und dixtra ist der Algorithmus von dexra findet die
- minimale des von einem bestimmten Knoten zu einem anderen Knoten der Algorithmus von Prim jedoch gibt einen minimalen Spannbaum eines gegebenen Grafen zurück
- 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
- 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
- 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
- zu verpassen bis zum nächsten Video tschüss
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 …