11_Algorithmen&Datenstrukturen || Graphen-Breitensuche (BFS)
Tutorial City
https://www.youtube.com/watch?v=hR4s2W7Dsss

Transkript (automatisch erstellt)

0:00 [Musik] hallo und herzlich willkommen bei Tutorial City heute geht es um den Teilbereich Breitensuche im englischen
0:14 DEP first search genannt wie auch bei der Tiefensuche werden die Knoten farblich markiert um sich ihren Status zu merken dabei steht die Farbe Rot für
0:23 einen unentdeckten Knoten wird ein Knoten entdeckt so wird er grün gefärbt und ist der Knoten blau gefärbt so gilt er als abgearbeitet bzw entfernter
0:32 Knoten bei der Initialisierung des Grafen werden alle Knoten standardmäßig mit dem Wert unendlich markiert anfangs wähle ich einen Startknoten aus und alle
0:42 anderen bekommen als Eigenwert die Entfernung zum Startknoten zugewiesen schauen wir uns das Ganze an einem Beispiel an hier haben wir unseren
0:51 Grafen und im Gegensatz zur Tiefensuche wird bei der Breitensuche mit einer Liste gearbeitet wir initialisieren alle Knoten mit unendlich und Sch kann es
1:00 losgehen als Startknoten wählen wir R wir markieren diesen grün geben ihm den Startwert Null und schreiben ihn in unsere
1:09 Liste nun überprüfen wir R auf seine Nachbarn wir markieren also S und U jeweils grün und beide bekommen den Wert 1 weil genau eine Kante zwischen R dem
1:20 Startknoten und S liegt bzw eine Kante zwischen R und U liegt nachdem beide Knoten eingefügt wurden ist der abgearbeit wird also blau
1:31 markiert und ist bereits aus der Liste entfernt nun schauen wir uns das nächste Element am Kopf der Liste an das ist s sein einziger unentdeckter Nachbar W
1:41 wird grün markiert und bekommt den Wert 2 weil zwei Kanten zwischen R dem Startknoten und W liegen S wurde aus der Liste entfernt und nun wird u
1:55 überprüft alle unentdeckten Nachbarn von U werden mit den Werten Z beschrieben und grün markiert gleiches wird wiederum für W
2:04 und V gemacht x und t haben allerdings keine weiteren Nachbarn werden also aus der
2:25 Liste entfernt und blau markiert Z wird als letztes von Y entdeckt und somit als letztes Element in die Liste
2:40 eingefügt Z wird grün markiert bekommt den Wert 4 und Y wird blau markiert und ist bereits aus der Liste entfernt Z wird also das das letzte Element ist nur
2:51 noch aus der Liste entfernt und blau markiert die Breitensuche ist einer der einfachstengor men für das Durchsuchen
3:00 eines Grafen und die beiden Algorithmen von Prim und dextra arbeiten mit diesem Algorithmus die Funktion dieser beiden Algorithmen von Prim und extra findet
3:10 ihr in meinem anderen Video wenn euch das Video gefallen hat dann bewertet es bitte gut und abonniert den Kanal um kein Video mehr zu verpassen bis zum
3:18 nächsten Video tschüss