Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Algorithmen und Datenstrukturen #38 - Tiefensuche
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 53 Zeilen
- Hallo ihr Lieben und Herzlich Willkommen zurück zu unseren Algorithmen. Dieses Mal tatsächlich mit den Algorithmen für Graphen.
- Und ja, wir werden heute selbstverständlich weitermachen und zwar mit dem Algorithmus Tiefensuche. Die Tiefensuche ist ein wunderbares Werkzeug, denn ja im Endeffekt ist es quasi Breitensuche nur in anders.
- Also er funktioniert anders, hat aber ein ähnliches Ergebnis, nur eine andere Reihenfolge und eine andere Arbeitsart. Und je nachdem was ihr erreichen wollt, um jeden Knoten einmal zu besuchen und damit irgendwelche Operationen zu machen,
- ist die Tiefensuche deutlich besser geeignet oder aber die Breitensuche ist deutlich besser geeignet. Es kommt immer drauf an, was ihr machen wollt.
- Und ich persönlich fand sogar die Tiefensuche immer ein bisschen leichter zu verstehen. Aber ja, ich glaube das wird euch, nun ja nach meinen Videos, sollte ihr beide verstanden haben, okay?
- Alles klar, so dann lasst uns mal beginnen und zwar die Tiefensuche fängt natürlich ähnlich an wie die Breitensuche. Wir haben auch hier ein Wizarded Array, wo als Boolean, also quasi als Wahrheitswert 0 oder 1 gespeichert wird.
- 0 heißt falsch, 1 heißt richtig oder wahr, ob der Knoten schon angeguckt wurde. Dann haben wir dieses Mal keine Queue, sondern ein Stack.
- Das ist der einzige große Unterschied und ihr werdet gleich sehen, was der Unterschied zwischen Queue und Stack hier bedeutet. Nämlich komplett, ob ihr eine Tiefensuche oder eine Breitensuche macht.
- Das ist der einzige wirkliche Unterschied, ansonsten arbeiten die Algorithmen quasi gleich. Und das ist absolut faszinierend, wie ich finde.
- Ja und dann haben wir hier noch die Ausgabe selbstverständlich wieder und genau. Okay, so die Tiefensuche beginnt in unserem Fall selbstverständlich auch bei Element 0.
- Oder bei Knoten 0 und wir packen hier selbstverständlich auch diesen Knoten 0 in unseren Stack rein und in unsere Ausgabe. So, wenn wir den Knoten 0 jetzt betrachten, dann machen wir nicht die Knoten 1 und 2 in unseren Stack rein.
- Sondern wir machen nur einen rein und verfolgen den dann. Das heißt, wir gehen eine der beiden Kanten entlang und welche Kante jetzt hier gewählt wird, ist entweder zufällig gewählt oder aber,
- also das ist die wahrscheinlichere Variante, ihr nehmt einfach die Kante, die in eurer Liste an Kanten eben zuerst kommt. Das heißt, ihr habt von mir aus eine Liste an Kanten, die von Knoten 0 ausgehen in eurer Implementierung drin.
- Und dort geht ihr jetzt einfach diese Kante entlang, weil die halt einfach zuerst da ist. Okay, das heißt wir gehen auf Knoten 1 und dementsprechend setzen wir hier auch unseren Knoten 1 auf visited.
- Packen diesen Knoten 1 in unseren Stack rein und dann geben wir natürlich noch den Knoten 1 aus. So, und jetzt machen wir nicht Knoten 2 rein, weil wir von 0 ausgehen, sondern wir gehen jetzt hier von Knoten 1 wieder aus.
- Und da kommt jetzt die Datenstruktur stack zum Einsatz. Ein Stack arbeitet sozusagen immer die neuesten Werte zuerst ab.
- Das heißt, der Wert 0 oder der Knoten 0 wird jetzt definitiv hinter dem Knoten 1 begutachtet, weil der Knoten 1 später hinzugefügt wurde.
- Das heißt, es ist im Endeffekt diese Struktur, dass immer das neueste Element als erstes bearbeitet wird. Dementsprechend gehen wir jetzt auch von Knoten 1 eine Kante weiter.
- Und hier haben wir Möglichkeiten auf 2, 3 oder 4 runter zu gehen. Und wie gesagt, das ist zufällig, beziehungsweise das kommt darauf an, wie ihr das eben implementiert habt,
- welche Kante zuerst in eurer Liste an Kanten drin steht. In meinem Fall dachte ich mir jetzt mal, wir gehen zur 4.
- Und dementsprechend sagen wir hier, okay, die 4 wurde besucht. Das heißt, wir müssen uns die 4 nicht nochmal angucken und das wird nachher noch gleich wichtig werden.
- Wir fügen die 4 in unseren Stack ein und wir geben selbstverständlich die 4 auch aus. So, jetzt gehen wir aber nicht mehr von der 1 weiter, sondern wir gehen von der 4 weiter.
- Und von der 4, naja, können wir entweder zur 3, zur 1 oder zur 2 gehen. Und wir gehen jetzt einfach mal hier zur 3, weil können wir.
- Und dementsprechend müssen wir natürlich hier sagen, okay, 3 wurde besucht. Die 3 kommt auf den Stack und wir geben die 3 auch aus.
- So, und jetzt sind wir hier bei der 3. Jetzt haben wir die Möglichkeit zur 1 zu gehen und zur 4 zu gehen.
- Wir wählen jetzt erstmal zufällig die 1 aus. Aber die 1, naja, die hatten wir ja schon.
- Die ist hier in unserem Wizarded Array hier auf 1 gesetzt. Das heißt, da waren wir schon.
- Okay, das heißt, diese Kante hier brauchen wir uns nicht angucken, beziehungsweise diesen Knoten brauchen wir uns nicht angucken.
- Also gehen wir zurück zur 3 und gucken uns die andere Kante an. Das wäre die zur 4.
- Ja, die 4, die haben wir uns aber auch schon angeguckt. Das heißt, wir sind fertig mit der 3, weil von der 3 können wir jetzt nirgends mehr hingehen.
- Und ihr habt es gesehen, die 3 verschwindet von unserem Stack. Das nächste Element auf unserem Stack obendrauf quasi ist die 4.
- Das heißt, die 4 sagt uns jetzt, okay, jetzt sind wir bei der 4. Und wir gehen jetzt von der 4 die Kanten entlang.
- Bei der 3 waren wir schon, da sind wir fertig. Jetzt sind wir wieder zu 4 zurückgekommen.
- Jetzt gehen wir zur 1, weil das von mir die nächste Implementierung ist. Und naja, da waren wir auch schon in unserem Wizarded Array.
- Sehen wir hier, okay, die 1 ist da gewesen. Das heißt, wir gehen wieder zur 4.
- Und die 4 sagt dann, okay, es gibt noch einen weiteren Knoten, nämlich die 2. Und die 2, naja, dann fügen wir eben die 2 in unseren Stack ein.
- Und setzen natürlich auch die 2 auf Wizarded, hier also auf 1 in unserem Wizarded Array. Packen hier natürlich die 2 in den Stack und geben die 2 aus.
- Und jetzt sind wir bei der 2 und schauen, was wir von der 2 erreichen können. Naja, die 1 und die 4 und die 0 auch.
- Haben wir aber alle 3 schon gemacht. Das heißt, die 2 ist auch fertig.
- Dementsprechend gehen wir wieder zurück zur 4. Und bei der 4 gibt es jetzt auch keine Option mehr.
- Das heißt, die 4 ist jetzt auch fertig. Und dann gehen wir wieder zurück zur 1.
- Und die 1 ist jetzt auch fertig, weil wir alle schon gemacht haben. Also, weil wir eben im Endeffekt im Wizarded Array uns gespeichert haben,
- dass jeder Knoten, der verfügbar ist von der 1, schon erreicht wurde. Und ja, dann gehen wir zurück zur 0.
- Und die 0, die haben wir auch. Und dementsprechend haben wir natürlich jeden Knoten hier begutachtet.
- So, ja, was bedeutet das jetzt für uns? Nun, wir können mit der Tiefensuche auch Sachen machen, wie zum Beispiel eben Labyrinthe lösen.
- Labyrinthe lösen finde ich eine super anschauliche Lösung, um tatsächlich hier eine Tiefensuche zu illustrieren quasi. Und deswegen möchte ich euch mal bitten, zeichnet euch mal ein Labyrinth auf.
- Und versucht mal hier tatsächlich einen Labyrinth-Löser nach Tiefensuchen-Prinzip drauf zu machen. Also versucht nicht den Code dafür zu schreiben, sondern versucht das wirklich nur auf dem Blatt Papier zu machen.
- Versucht hier zu sagen, die Knoten sind die Punkte, wo ich abbiegen kann. Die Knoten sind die Punkte, wo ich abbiegen kann.
- Und, ja, Sackgassen sind natürlich auch Knoten, also quasi das Ende eines Weges ist auch ein Knoten. Genau, und das ist es eigentlich auch schon.
- Und damit könnt ihr dann auch Sortierungen machen, Min-Spanning-Trees, wobei wir da noch nicht mal drauf kommen können, weil die sind ein bisschen komplexer. Und so weiter und so fort.
- Und, ja, wie gesagt, Tiefensuche ist auch ein Grundalgorithmus, von dem man ausgehen kann. Und da kann man dann noch viel, viel coolere Sachen dann drauf bauen.
- Okay, das war's von meiner Seite. Wir hören uns wieder beim nächsten Mal.
- Bis dann, ciao.
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 …
Beschränkte TiefensucheBeschränkte Tiefensuche (englisch depth-limited search, DLS) ist in der Informatik ein Verfahren zum Suchen eines Knotens in einem Graphen.
Iterative TiefensucheDie iterative Tiefensuche (englisch iterative deepening depth-first search, IDDFS) ist ein Verfahren aus der Informatik zum Suchen eines Knotens in einem …
BreitensucheBreitensuche (englisch breadth-first search, BFS) ist ein Verfahren in der Informatik zum Durchsuchen bzw. Durchlaufen der Knoten eines Graphen.