Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Kruskal: Informatik (deutsch)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 24 Zeilen
- hallo und herzlich willkommen in meiner informatikecke heute möchte ich euch den kruskal Algorithmus zeigen der kruskalalgorithmus berechnet
- einen minimalen Spannbaum in einem Grafen dazu muss der Graf allerdings einige Voraussetzungen haben er muss nämlich ungerichtet sein und die Kanten
- müssen gewichtet sein außerdem sollte er natürlich noch zusammenhängen und endlich sein aber das ist ja denke ich mal ganz klar für was braucht man solche
- spannbäume überhaupt mit denen könnte ich jetzt z.B feststellen wie die ganzen kürzesten Wege von allen Punkten zueinander
- sind dann fangen wir auch gleich mal an der Algorithmus ist eigentlich ziemlich einfach rechts möchte ich auch noch antragen welche Knoten wir schon besucht
- haben bei krükall geht man so vor dass man sich die die Kantengewichte betrachtet und sie aufsteigend sortiert das heißt ich suche mir jetzt die
- kleinste Kante die ich erstmal finden kann in dem Fall habe ich zwei Kanten mit dem kantengewicht 2 das ist die hier unten und die hier oben welche ich jetzt
- davon nehme ist erstmal ziemlich egal in meinem Fall nehme ich mal die Kante hier
- unten und in diesem Fall sind die Knoten h und G schon besucht denn die sind jetzt in unserem Spannbaum den wir ja aufrichten
- wollen schon enthalten das heißt g und h kann ich mir schon mal merken danach suche ich wieder die kleinste Kante im ganzen Grafen aber die
- die ich schon markiert habe die kann ich außen vorlassen das heißt diesmal nehme ich jetzt die andere zwei und jetzt sind auch C und D Knoten
- die schon erreichbar sind dann geht's weiter das nächst kleine kantengewicht wäre ja dre da
- haben wir auch schon zwei genau zwei Kanten mit dem kantengewicht 3 dann nehme ich als nächstes z.B die hier oben dann kann ich
- B mit antragen und dann nehme ich noch die hier und ich kann A mit antragen so das nächst kleinste kantengewicht das
- wir finden könnten wäre 4 das haben wir einmal hier unten das heißt F kann ich mit antragen und wir
- haben die vier hier oben die Kante hier die darf ich jetzt allerdings nicht nehmen denn es würde ein Zyklus entstehen und ein Spannbaum darf kein
- Zyklus enthalten also ein Zyklus heißt dass hier praktisch so ein ein Kreis entsteht zwischen A A B C und D würde ich hier Kreis entstehen das darf nicht
- passieren deswegen darf ich diese Kante nicht nehmen und lass die einfach aus das nächste Gewicht das wir finden können ist die
- F die haben wir auch mehrmals die hier oben darf ich wieder nicht nehmen weil sonst ein Zyklus entsteht
- deswegen nehme ich diese fünf hier kann dann das E noch mitanttragen und ganz zum Schluss nehme ich
- noch diese fünf und wir sehen jetzt alle Knoten stehen schon unter besucht und unser ganzes Gebilde ist jetzt
- zusammenhängend und damit sind wir am Ende damit terminiert der Algorithmus das war's auch schon zu kruskal der ist eigentlich nicht sehr
- kompliziert und wie immer gibt's zum Schluss eine kleine Aufgabe ihr dürft den krükeilalgorithmus jetzt an dem gleichen Grafen hier ausprobieren aber
- diesmal sucht ihr nicht den minimalen Spannbaum sondern den maximalen Spannbaum Lösung gibt's wie immer unter dem Video bis zum nächsten Mal tschüss
Zum Nachlesen
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 PrimDer Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen.
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 …
SpannbaumEin Spannbaum eines Graphen kann in linearer Zeit entweder durch Tiefensuche oder durch Breitensuche gefunden werden. Beide Algorithmen untersuchen den …