10_Algorithmen&Datenstrukturen || Graphen-Tiefensuche (DFS)
Tutorial City
https://www.youtube.com/watch?v=gDx74JDj_yM

Transkript (automatisch erstellt)

0:00 [Musik] herzlich willkommen bei Tutorial City heute geht es um Grafen insbesondere um die tiefenuche wie bei der breitenuche
0:16 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
0:25 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
0:37 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
0:47 bevor wir uns das Ganze an einem Beispiel verdeutlichen um nachzuvollziehen wie die Tiefensuche funktioniert schauen wir uns erst noch
0:54 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
1:06 Nachbarn sind in diesem Fall alphabetisch sortiert diese alphabetisch sortierte Liste nennt man adjazenzliste der Knoten a hat zwei ausgehende Pfeile
1:15 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
1:25 adjazzenzlisten erstellt bis alle Knoten auf Nachbarn überprüft wurden kommen wir zum Beispiel hier haben wir einen Grafen mit
1:35 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
1:46 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
1:55 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
2:05 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
2:14 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
2:25 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
2:36 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
2:47 Element in der adenzliste und wird als entdeckt markiert bekommt auch einen Zeitstempel fürs entdecken und gleich ein Zeitstempel der finishzeit da kein
2:57 weiteres Element in der adzenzliste von Z ist dies wird so lange gemacht bis alle Knoten ihre Discovery und Finish Zeit haben
3:31 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
3:39 verpassen bis zum nächsten Video tschüss