Kruskal: Informatik (deutsch)
bleeptrack
https://www.youtube.com/watch?v=GJ17vvqY6aE

Transkript (automatisch erstellt)

0:01 hallo und herzlich willkommen in meiner informatikecke heute möchte ich euch den kruskal Algorithmus zeigen der kruskalalgorithmus berechnet
0:12 einen minimalen Spannbaum in einem Grafen dazu muss der Graf allerdings einige Voraussetzungen haben er muss nämlich ungerichtet sein und die Kanten
0:23 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
0:33 spannbäume überhaupt mit denen könnte ich jetzt z.B feststellen wie die ganzen kürzesten Wege von allen Punkten zueinander
0:45 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
0:55 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
1:06 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
1:19 davon nehme ist erstmal ziemlich egal in meinem Fall nehme ich mal die Kante hier
1:30 unten und in diesem Fall sind die Knoten h und G schon besucht denn die sind jetzt in unserem Spannbaum den wir ja aufrichten
1:39 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
1:51 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
2:00 die schon erreichbar sind dann geht's weiter das nächst kleine kantengewicht wäre ja dre da
2:10 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
2:21 B mit antragen und dann nehme ich noch die hier und ich kann A mit antragen so das nächst kleinste kantengewicht das
2:34 wir finden könnten wäre 4 das haben wir einmal hier unten das heißt F kann ich mit antragen und wir
2:44 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
2:54 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
3:03 passieren deswegen darf ich diese Kante nicht nehmen und lass die einfach aus das nächste Gewicht das wir finden können ist die
3:11 F die haben wir auch mehrmals die hier oben darf ich wieder nicht nehmen weil sonst ein Zyklus entsteht
3:22 deswegen nehme ich diese fünf hier kann dann das E noch mitanttragen und ganz zum Schluss nehme ich
3:32 noch diese fünf und wir sehen jetzt alle Knoten stehen schon unter besucht und unser ganzes Gebilde ist jetzt
3:45 zusammenhängend und damit sind wir am Ende damit terminiert der Algorithmus das war's auch schon zu kruskal der ist eigentlich nicht sehr
3:56 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
4:06 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