Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Graphen durchsuchen: Tiefensuche
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 44 Zeilen
- [Musik] [Musik]
- und zwei strategien beim durchsuchen von graphen oder bäumen ist die tiefen suche das ist vermutlich auch die kürzere variante aber nicht immer die beste
- nicht desto trotz sehen wir uns jetzt anbietet tiefen funktionen auf die tiefen suche genau funktioniert so wir haben wieder unseren bekannten grafen
- mit einer darunter abgebildet adac matrix beziehungsweise adac liste und wir werden uns jetzt grafisch ansehen wie diese algorithmus der tiefen suche
- eigentlich funktioniert und wie diese mit hilfe der adac liste aber auch die adac matrix abgebildet wird also wie werden die daten nacheinander durchsucht
- als erstes brauchen wir wieder unser indem wir ein schreiben welche knoten haben wir im graben bereits besucht damit wir nicht in endlosschleifen
- kommen ja nicht dass der graf vom 183 nach 4 nach 1 nach 3 nach 4 nach 1 nach 304 durchsucht wird immer wieder und der computer hier nicht mehr raus kommt
- deswegen werden wir uns alle elemente die wir bereits durchsucht haben in dieser sogenannten visit lässt gut wir fangen irgendwann also oben oder vorne
- wie man das sehen wir beim grafen also wir fangen einfach bei einem seien so bei der tiefen suche wird jetzt das erste kind also zu beginn noch wir mehr
- uns natürlich in der wz ist so beide tiefen suche wird das erstbeste kinder also der erste nachbar einfach verwendet und gleich in diesem weitergesucht der
- erstbeste nachbar ist bei uns die drei ja unten auch mit dem plan dargestellt in der derzeit listet das erste element ist die drei in der adac matrix
- ebenfalls das erste element des 23 wir merken uns dass wir die drei jetzt besucht haben wieder in unserer suchliste sozusagen und gehen jetzt zu
- der drei und sagen okay was ist das erste element aber vorsicht das noch nicht in der besuchsliste ist wie man in der hat
- jetzt ein smart tricks und lässt sie sehen würde wäre das erste element wieder die einst das ist natürlich nicht in der sache denn dann hätten wir die
- ender schleife deswegen nehmen wir das erste element das nicht bereits in der besuchsliste ist und das ist dann die 4 so also weiter gegangen zur 4 d-4d
- besuchsliste mit aufgenommen so auch die vier nimmt das erstbeste element den ersten nachbarn der erstbeste nachbar wäre die 11 ist
- allerdings bereits in der besuchsliste anzunehmen wird demnächst in der liste das wäre die 56 wird jetzt total ignoriert ja jetzt könnte man sagen okay
- es nächster sollte er die sechs durchsuchen nein mache eine tiefen suche das heißt wir gehen den weg fertig so lange wir können also wir sind von der 1
- 2 3 von der drei zu viel von der 45 und jetzt sehen wir machen wir das gleiche spiel bei der 56 wird ignoriert also wir gehen zur 5 nehmen der fünfte
- besuchsliste auf anschließend sehen wir uns den erstbesten nachbarn an das ist die 2 nehmen diese in die besucherliste auf und nehmen jetzt wieder den
- erstbesten nachbarn denn wir finden und das wäre in diesem fall die sechs so wenn wir die sechs gefunden haben sehen wir schlussendlich dass es hier keine
- nachbarn mehr gibt also jetzt können wir schauen es gibt keine nachbar mir wir sehen uns auch in der drc liste das ist nichts in dieser liste die sozusagen
- leer also sind wir jetzt in der ersten situation die gesamte tiefe durchgegangen es geht hier nicht mehr
- weiter das heißt aber nicht dass wir fertig sind das heißt nur wir haben den einen weg mal bis ganz kunden gemacht es kann noch andere wege geben nur bei der
- 6 gezahlt nicht weiter also gehen wir einen schritt zurück und sagen wie sie es bei der 2 aus naja die zwei hat außer der sechs und die haben
- wir bereits besucht auch keine elemente mehr keine nachbar mir die durchsucht werden sollen also wieder einen schritt zurück zu 5
- das ganze hier wieder gemacht ja die fünf hat nur aus nachbarn die zwei also auch nichts weiteres wo wir durchsuchen können also zurück zur 4
- so bei der vier sehen wir jetzt okay es gibt die einst allerdings ist ja die ist schon in der besucher haben wir die vorher schon ausgeschlossen weil sie
- schon in der besuchsliste war jetzt gibt es noch einen nachbarn der nächste logische werte 6 allerdings ist es auch schon in der besuchsliste
- trennen deswegen gehen wir auch mit der sex nicht weiter allerdings wer die sechs noch nicht in der besuchsliste gewesen würde jetzt diese ganze rhythmus
- wieder weiter zunächst zum ersten nachbarn zum erstbesten nachbarn genauso weiter ging in diesem fall brauchen wir nicht wir schon wieder eins zurück 23
- wir schauen wieder ein zurück zur 1 wir haben in diesem fall der ersten suche bereits alle sechs elemente gefunden oder durchsucht und haben deswegen beim
- zurück schon nichts mehr gekommen allerdings kann das wie gesagt durchaus der fasern oder ist auch die regelfall vor allem in bäumen nur diese spezielle
- graf hat das eben nicht so dass nach vorne schauen ist wahrscheinlich jetzt recht eingängig gewesen wie geht das also nimm den erstbesten nachbarn in
- denen du in die zeile bzw in der liste nach schaust wie es denn das wie wird das mit dem zurück um dort wieder weiter sehen
- im endeffekt ist diese ganze rum was einfach nur eine revision um wenn die rezession zu ende ist dann macht die automatische einen schritt zurück das
- heißt normalerweise ist das nichts anderes wie man nimmt das erste einen knoten schmeißt diesen knoten in einer funktion geht dadurch bricht wenn dieser
- bereits in der besuchsliste ist geht aus der funktion raus ansonsten geht er jeden nachbarn durch in einer schleife und ruft
- die diskussion selbst wieder auf dadurch wird jeder nachbar der noch nicht in der besuchsliste ist durchsucht aber es ist automatisch genau so einen
- tiefen suche wie wir sie hier jetzt grafisch gesehen haben der zwei tage rhythmus ist die breiten suche breiten suche gibt es in einem
- anderen video wenn es ein praxisbeispiel dazu geben sollte oder wenn wenn es holt kein ding seht euch die grafen algorithmen an die bereits da sind da
- gibt es zum beispiel das thema der weg findung ist bereits implementiert nach genau diesen schema der tiefen suche in diesem sinne ich hoffe es hat euch
- gefallen lassen aber hier und viel spaß bis zum nächsten mal und wenns euch gefallen hat erst ein abo da
- [Musik]
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 …
DatenstrukturIn der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine …
AlgorithmusAlgorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten. ... Damit können sie zur Ausführung in ein Computerprogramm implementiert, aber auch in …
InformatikAls einfache Rechengeräte leisteten Abakus und später der Rechenschieber unschätzbare Dienste. 1641 konstruierte Blaise Pascal eine mechanische …