Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
11_Algorithmen&Datenstrukturen || Graphen-Breitensuche (BFS)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 19 Zeilen
- [Musik] hallo und herzlich willkommen bei Tutorial City heute geht es um den Teilbereich Breitensuche im englischen
- 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
- 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
- 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
- anderen bekommen als Eigenwert die Entfernung zum Startknoten zugewiesen schauen wir uns das Ganze an einem Beispiel an hier haben wir unseren
- Grafen und im Gegensatz zur Tiefensuche wird bei der Breitensuche mit einer Liste gearbeitet wir initialisieren alle Knoten mit unendlich und Sch kann es
- losgehen als Startknoten wählen wir R wir markieren diesen grün geben ihm den Startwert Null und schreiben ihn in unsere
- 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
- Startknoten und S liegt bzw eine Kante zwischen R und U liegt nachdem beide Knoten eingefügt wurden ist der abgearbeit wird also blau
- 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
- 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
- überprüft alle unentdeckten Nachbarn von U werden mit den Werten Z beschrieben und grün markiert gleiches wird wiederum für W
- und V gemacht x und t haben allerdings keine weiteren Nachbarn werden also aus der
- Liste entfernt und blau markiert Z wird als letztes von Y entdeckt und somit als letztes Element in die Liste
- 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
- noch aus der Liste entfernt und blau markiert die Breitensuche ist einer der einfachstengor men für das Durchsuchen
- eines Grafen und die beiden Algorithmen von Prim und dextra arbeiten mit diesem Algorithmus die Funktion dieser beiden Algorithmen von Prim und extra findet
- 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
- nächsten Video tschüss
Zum Nachlesen
BreitensucheBreitensuche (englisch breadth-first search, BFS) ist ein Verfahren in der Informatik zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphen.
TiefensucheTiefensuche (englisch depth-first search, DFS) ist in der Informatik ein Verfahren zum Suchen von Knoten in einem Graphen. Sie zählt zu den uninformierten …
Parallele BreitensucheDie parallele Breitensuche (englisch parallel breadth-first search (BFS)) ist in der Informatik eine Variante des Breitensuche-Algorithmus für Graphen, bei …
Iterative TiefensucheDie iterative Tiefensuche (englisch iterative deepening depth-first search, IDDFS) ist ein Verfahren aus der Informatik zum Suchen eines Knotens in einem …