Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
10_Algorithmen&Datenstrukturen || Graphen-Tiefensuche (DFS)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 20 Zeilen
- [Musik] herzlich willkommen bei Tutorial City heute geht es um Grafen insbesondere um die tiefenuche wie bei der breitenuche
- fähbt die Tiefensuche die Knoten während den durchsuchen eines grafens um sich ihre Zustände zu merken jeder Knoten ist anfangs rot wird grün gefärbt wenn er
- entdeckt wird und blau gefärbt sobald er komplett abgearbeitet ist und aus dem Stapel entfernt wurde außerdem hat jeder Knoten zwei Zeitstempel DT steht für das
- covery time also den Zeitpunkt wann der Knoten entdeckt wurde FT beschreibt die Finish time also den Zeitpunkt wenn der Knoten aus dem Stabel entfernt wird
- bevor wir uns das Ganze an einem Beispiel verdeutlichen um nachzuvollziehen wie die Tiefensuche funktioniert schauen wir uns erst noch
- an was eigentlich adjazenzlisten sind wir haben diesen Grafen mit den Knoten A bis F für jeden Knoten existiert eine eigene Liste mit seinen Nachbarn diese
- Nachbarn sind in diesem Fall alphabetisch sortiert diese alphabetisch sortierte Liste nennt man adjazenzliste der Knoten a hat zwei ausgehende Pfeile
- nach B und D das sind also seine zwei Nachbarn B hat nur einen ausgehenden Fall nach E also ist das wiederum sein einziger Nachbar so werden die
- adjazzenzlisten erstellt bis alle Knoten auf Nachbarn überprüft wurden kommen wir zum Beispiel hier haben wir einen Grafen mit
- den Knoten R bis Z und einen Stapel oder auch Deck indem wir die Knoten speichern als einzige Vorgabe geben wir uns wenn die Wahl bleibt nehme zuerst
- den Knoten der im Alphabet als nächstes folgt das heißt wir versuchen sofern es möglich ist die Knoten alphabetisch zu ordnen beginnen wir als erstes mit dem
- Knoten R wir markieren diesen grün geben ihm die entdeckungszeit 1 fügen ihn nun in den Stapel ein und schauen jetzt in der adiazenzliste von R nach welcher
- Knoten als nächstes in der alphabetischen Reihenfolge folgen würde das ist der Knoten s dieser wird grün markiert bekommt die entdeckungszeit 2
- und wird in den Stapel eingefügt in der adiazenzliste von S folgt W W wird wieder grün markiert wurde als dritter entdeckt und wird in den Stapel
- eingefügt jetzt wird t als nächstes entdeckt markiert und bekommt den Wert vi allerdings hat t keine Nachbarn da die adiazenzliste leer ist gilt sie als
- komplett durchlaufen t bekommt die finishzeit 5 wird somit blau gefärbt und aus dem Stapel gelöscht wir kehren zurück zur W hier ist noch Z als letztes
- Element in der adenzliste und wird als entdeckt markiert bekommt auch einen Zeitstempel fürs entdecken und gleich ein Zeitstempel der finishzeit da kein
- weiteres Element in der adzenzliste von Z ist dies wird so lange gemacht bis alle Knoten ihre Discovery und Finish Zeit haben
- das war's zum Thema Tiefensuche in Grafen 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
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 …
BreitensucheBreitensuche (englisch breadth-first search, BFS) ist ein Verfahren in der Informatik zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphen.
Diskrete MathematikInsbesondere spielt die Stetigkeit in der Diskreten Mathematik keine Rolle. Die in der Diskreten Mathematik vertretenen Gebiete (wie etwa die Zahlentheorie …