Video 11-6: Tiefensuche (Teil 2)

0:04 Bevor wir jetzt uns den Code genauer anschauen, möchte ich erstmal eine intuitive Version noch mal zeigen. Ähm, zuerst in der metaphorischen Version. Ähm, ein paar Sachen, die Sie hier sehen können, sind einerseits hier ist der Graf gemalt. Ähm, wir werden den später eigentlich immer so malen als Knot. eher so als Knoten mit Kanten dazwischen mit Strichen. Für den Moment schauen wir uns den aber mal so an, wie er als Labyrinth aussehen würde mit Kreuzungen und äh Korridoren dazwischen. Im Computer repräsentiert ist ein Graf, wie wir letztes Mal besprochen haben, in aller Regel als Adjazlisten, wenn nichts anderes irgendwo äh Sinn macht aus Spezialgründen. Das heißt, wir haben die Knoten von 0 bis äh Anzahl Knoten -1 durchnummeriert und die Liste selbst für jeden Knoten Liste die Nachbarn.

1:09 Ähm, wir haben hier einen ungerichteten Grafen. Das heißt, wenn es diese Kante 08 gibt, hier die null ist, wo wir aktuell stehen, dann gibt's von 0 den Eintrag 8. Es gibt aber auch bei der 8 den Eintrag null. kann also die Korridore in beide Richtungen verwenden.

1:26 Wie würde man jetzt ähm systematischer vorgehen, diesen Korridor zu durchschreiten? Äh vielleicht erstmal in der langsamen Version. Wir stehen aktuell in diesem Knoten null und jetzt kann ich mir in diesen Korridoren anschauen, wo ich als nächstes hingehen kann. Wir folgen aber hier immer den Reihenfolge der Adjazliste. Werden Sie dann gleich noch mal sehen, ähm, dass wir da sehr ähm strukturiert vorgehen.

1:52 Äh wir haben dann hier einen einen Korridor, den wir noch nicht ausprobiert haben. Das heißt, wir laufen den entlang, markieren uns, dass wir da nicht noch mal lang gehen und dann laufen wir den Korridor lang und ziehen den roten Faden hinter uns her. Wenn wir den neuen Knoten betreten wir jetzt hier den Knoten 8, dann habe ich wieder in der Adjazliste ausgehende Kanten. Eine ist natürlich die, über die ich gerade hier reinkam. Das ist die erste hier. Deswegen markieren wir die jetzt als Da war ich schon, brauche ich nicht noch mal explorieren. Und die beiden anderen Kanten schaue ich mir danach an. Und bei der Tiefensuche ist der Punkt, ich gehe immer erstmal so weit in das Labyrinth rein wie möglich. Also, wenn ich jetzt hier diese Kante zur neun sehe, das ist die nächste, die hier in der Liste ist, dann markiere ich die, dass ich da nicht noch mal lang gehe in der Zukunft. Und dann laufe ich lang, rolle meinen Faden ab und mach von dort weiter.

2:48 Ich gehe also immer erstmal so weit in die Tiefe ähm wie möglich und wir lassen das mal langsam laufen und sie verfolgen das ein bisschen. Hier gibt's so ein paar Zwischenknoten, an denen ich ja gar keine Auswahl hatte. An den Stellen hier ähm gab's eine Auswahl bei dem Knoten 5 und die hat jetzt gesagt, wir sollen zuerst die 12, da kamen wir her prüfen. Na ja, die haben wir dann direkt abgehakt, da ist das Kreuz. Danach sind wir zur sechs statt zur vier. Das heißt, wir laufen hier in diese Sackgasse zurück. An der Stelle ähm ist vielleicht hilfreich noch mal kurz genauer drauf zu schauen, was passiert. Also, wir gehen in diesen Knoten 7. Und jetzt stelle ich fest, ähm es gibt hier noch einen Korridor, den ich noch nicht probiert habe. Den habe ich auch in der aus der anderen Richtung noch nicht probiert. Der führt aber zu einem Knoten, wo ich schon war. Das habe ich mir gemerkt. Und der ist ja tatsächlich hier auch noch auf den ähm im im hat noch einen Faden, der durch die Kreuzung durchläuft. Das heißt, ich gehe jetzt nicht noch mal zu diesem Knoten. Da war ich da war ich schon oder da ähm äh den habe ich schon einmal betreten und ich drehe hier sozusagen um und gehe dann meinen Weg zurück, markiere die diese Passage auch und komm wieder zurück zu meinem Knoten 5. Und sie sehen jetzt an der Stelle habe ich auch meinen Faden wieder abgerollt.

4:16 Sie sehen aber noch hier diese äh Schleimspur, die sozusagen verbleibt. Ich habe ja die Kanten markiert oder die Korridore markiert als hier war ich schon, hier gehe ich nicht noch mal rein. Der Faden ist immer nur auf dem direkten Weg, wie ich wieder zum Ausgang zurückkäme. Und sie können sich vorstellen, dass so ein Gummiband, wenn ich einen so einen so einen äh Weg hin und wieder zurückgehe, dann schnurrt das Band wieder zusammen und äh ist hier wieder am dem kürzesten Weg entlang. Ich werde die ganze Vorlesung sehr viel in blumigen und bildlichen Metaphern reden in der Hoffnung, dass das die Sachen ein bisschen besser im Gedächtnis verankert. Wir werden natürlich dann auch über den Informatikteil dahinter sprechen, wie das dann tatsächlich funktioniert und dass da keine Gummibänder im Spiel sind. Aber für den Moment ist, glaube ich, hilfreich, wenn sie erstmal die richtige Metapher im Kopf haben, dann sind die Dinge intuitiver. Von hier gehen wir jetzt weiter zur vier und verfolgen da auch wieder unsere Kanten. Markieren schön. Gehen wir jetzt hier in diese andere Sackasse. Sehen wir von außen natürlich, dass das nicht weiterführen wird. Passiert das gleiche wie eben. Hier war ich schon. Das heißt, ich gehe zurück und jetzt komme ich am Ende dann an meinem Startpunkt an. Die Null habe ich schon besucht, das heißt, da gehe ich nicht wieder rein. Ich muss aber jetzt hier noch manche Knoten wieder abschließen.

5:35 Sie sehen, es gibt diese dunklen äh die dunkel eingefärbten Knoten, bei denen habe ich alle ausgehenden Korridore mit einem Kreuz markiert. Das ist für diese hier teilweise noch nicht der Fall, denn der Rückweg ist noch nicht markiert. Ja, hier fehlt das Kreuz von 9 zurück zur 8 und so weiter. Äh, die habe ich noch nicht endgültig verlassen. Von der acht fehlt übrigens nicht der Rückweg zur null, sondern der Weg zur sieben. Ist in der Zeichnung, glaube ich, jetzt ähm nicht so gut zu erkennen, aber äh wenn wir dann da sind, sehen Sie, da kommt jetzt da ist ein Kreuz noch dazu gekommen, aber ich muss schon brauch schon eine Lupe. Na ja. Ähm, gut. Und dann sind wir zurück und jetzt haben wir alles abgearbeitet und haben den den ganzen Pfad durchschritten. Okay, also das ist die Intuition. Wir schleifen diesen Faden hinter uns her und markieren Korridore, wo wir schon waren. Was machen wir im Code tatsächlich?

6:36 Das ist nicht schrecklich anders. Äh, wir haben ein paar Sachen, die eigentlich fast einfacher sind. Änderung 1. Wir merken uns nur, in welchen Knoten wir schon waren. Wir markieren nicht wirklich Korridore. Äh, das Korridore markieren ist implizit. Ich habe die Adjazenlisten von meinem Graf und ich merke mir eine Position in dieser Liste. Alles, was vor der Position ist, weiter links habe ich schon den Korridor markiert. Alles, was danach kommt habe ich noch nicht gesehen. Ich mache also nicht wirklich eine Markierung an die Kanten. Ich habe das implizit im Ablauf vom Algorithmus. Und äh der Ariatmefaden ist letztlich ein ein Stack, auf den wir immer einen Knoten legen. Also noch mal das gleiche Spiel, aber jetzt sozusagen die Informatiksichtweise. Ähm, wir fangen in unserem Knoten null an. Ein Schritt bedeutet, ich schaue mir den nächsten Eintrag in der Adiazzliste von diesem aktuellen Knoten an. Der erste Eintrag hier ist die acht. Das heißt, das äh ist die Kante, die ich anschaue. Acht ist ein Knoten, den ich noch nicht betreten habe. Das heißt, ich gehe da jetzt hin und pack den auf meinen Stack oben drauf. Damit ist dieser Schritt abgeschlossen. Das einzige, was ich noch markiere, ist in meiner Adjazliste drücke ich einen Schritt weiter. Wenn Sie sich vorstellen, wie die Adiazenzlisten in Java implementiert sind, dann ist es ein Iterator und der hat eine Next Methode, die macht das sogar beides in einem Schritt. Sie kriegen diesen Knoten 8 zurückgegeben und der rückt gleich weiter auf die nächste Position.

8:11 Jetzt kommt der nächste Schritt. Im Allgemeinen ist ein Schritt immer. Nimm den obersten Knoten vom Stack. Schaue dir das dessen Adjazsliste an. Wo bin ich da stehen geblieben? Bei der acht waren wir noch nicht, also am Anfang. Und dann prüfe, ob es ob wir diesen Knoten schon gesehen haben, ob wir da schon waren. Und Knoten null kamen wir her. Das heißt, der ist schon markiert als schon mal besucht. Dementsprechend machen wir mit der Kante einfach gar nichts und äh rücken in der Adzenliste einfach vor. Damit ist der Schritt zu Ende. Der nächste Schritt findet natürlich immer noch den gleichen Knoten oben auf dem Stack. Wir haben den ja nicht verändert, den Stack. Das heißt, ich prüfe den gleichen Knoten noch mal, aber jetzt mit dem nächsten Eintrage der Adiazzliste. Das ist die neun. Also gehe ich, weil den Knoten, weil ich den noch nicht besucht habe, gehe ich dahin. Und so arbeiten wir uns dadurch. Der allgemeine Schritt ist immer gleich.

9:08 Nimm den obersten Knoten vom Stack, nimm den nächsten Eintrag in seiner Adjazliste und dann gibt's zwei Fälle. Entweder war ich da schon oder ich war da noch nicht. Wenn ich da schon war, dann fertig, machen wir nichts. Wenn wir da noch nicht waren, dann gehen wir jetzt dahin und packen diesen Knoten auf den Stack.

9:32 das Beispiel ja schon gesehen. Ähm es passiert genau das gleiche, worauf ich ähm ihr in Fokus legen möchte, ist schauen Sie an, was mit den Adjazlisten passiert. Wir sind hier bei der sieben. Wenn wir am Ende angekommen sind, dann wird der Knoten als endgültig verlassen markiert. Wir werden den nicht noch mal sehen. Alles abgearbeitet.

10:01 Und hier entdecken wir diese ähm diesen Kreis, den wir äh da schließen könnten und dann am Ende rollen wir uns den Faden rückwärts ab, dann wird der Stack nur noch abgeräumt. Alle weiteren Knoten haben wir ja schon gesehen.

10:28 soweit erstmal zur Animation. Das ist die Idee dahinter. ein paar Details jetzt noch, wie wir das im im Code umsetzen. Erstmal brauchen wir ein paar Datenstrukturen, die ich schon erwähnt hatte, äh die aber in der Animation teilweise nur implizit sind in den Farben. Wir müssen uns merken, ob wir einen Knoten schon betreten haben. Das heißt, wir haben ein ähm werden ein Array verwenden, ein bulles Array, was einfach sagt, ob der Knoten schon betreten wurde oder nicht. Initial natürlich alle nicht.

11:00 Und man kann diese Tiefensuche wunderschön als eine rekursive Prozedur beschreiben. Dann ist der Stack der implizite Aufrufstack von Java. Ähm, also das Array, das äh markiert, ob die Knoten schon besucht sind, heißt Marked. Äh, wir können uns auch noch merken, ähm über welchen Knoten haben wir einen anderen Knoten das erste Mal betreten. Das hatte ich äh hier nicht explizit betont. Sie sehen es aber in der Animation. Äh, es gibt hier diese dunklen Kanten, die auch dunkel geblieben sind. Das ist die Kante, über die ich einen Knoten betreten habe, also von der 0 zur 8 zur 9 und so weiter. Und das ist sozusagen die Reihenfolge, in der wir die Knoten abgelaufen sind, aber ohne dass wir uns merken, die zeitliche Reihenfolge genau, sondern nur ähm für jeden Knoten, über welche Kante wurde er das erste Mal betreten. Äh, das vielleicht jetzt noch ein bisschen unklar, warum wir uns das merken wollen. Äh kommen wir gleich drauf zurück. Das ist ein ein Kern, auf dem dann viele Algorithmen aufbauen. Das können wir uns merken in Array, das einfach für jeden Knoten den Vorgänger speichert, über den wir diesen Knoten betreten haben.

12:19 Okay, sieht im Code sehr sehr kompakt aus. Der Hauptteil ist diese rekursive Methode. Wir rufen auf unserem Graf für den bestimmten Knoten, den wir jetzt als nächstes besuchen, dieses diese rekursive Methode Dep First Search auf. Dann merken wir uns, dass wir den jetzt betreten, damit wir das für die für folgende Aufrufe wissen. Und dann gehen wir durch seine ausgehenden Kanten Schritt für Schritt durch. Also für jeden Knoten W, der eine Kante von V hat, wenn der schon markiert ist, machen wir nichts. Das war dieses wir prüfen die gelbe Kante. Im Code macht es eigentlich gar nichts. Äh falls sie noch nicht, falls dieser Knoten noch nicht besucht ist, rufen wir rekursiv diese Dep First Search Methode da auf und wir merken uns noch, dass die Kante, die zu diesem Knoten W das erste Mal geführt hat, die Kante von uns war. Das ist ähm klar, dass hier W das erste Mal erreicht wurde, denn das haben wir gerade vorher geprüft. Okay, was können wir über diese ähm über diese Tiefensuche sagen? Ähm, erstmal sind am Ende alle Knoten markiert, die ich von meinem Startknoten aus erreichen kann.

13:44 Das ist eine Eigenschaft von den äh von Grafen im Allgemeinen, die nicht immer unbedingt gilt. Ich kann auch ähm Grafen haben wie dieser hier, der einfach gar nicht zusammenhängend ist, dann kann ich meine Tiefensuche von irgendwo an einem Knoten starten und ich werde natürlich nur die Knoten erreichen, über für die es irgendwie einen Weg von meinem Startknoten aus gibt. Also eine Anwendung von dieser Tiefensuche ist Zusammenhangskomponenten in dem Graf zu finden. Wir sehen das hier optisch natürlich sehr direkt, welche Teile verbunden sind, aber ähm in einem großen Graf mit komplizierten, wenn man das nicht so schön malen kann, äh dann ist Tiefensucher der richtige Weg, das zu prüfen.

14:34 Äh, die Aussage ist, dass die Tiefensuche also alle erreichbaren Knoten, alle von von dem Startknoten aus erreichbaren Knoten ähm in ist wesentlichen Linearzeit findet, also proportional zur äh Summe ihrer gerade ähm könnte man sagen linear finden in der Anzahl Knoten und der Anzahl Kanten schreiben wir dann in aller Regel als Konotation mit dem Plus. Eigentlich ist es mehr so das Maximum als das Plus, aber sie wissen vielleicht noch vom Anfang, das ist man konstante Faktoren ignoriert das gleiche. Ähm, der Beweis ist nur so eine Begründung letztlich ähm wenn ich einen Knoten ähm markiert habe, dann ähm gibt es auch einen Pfad dahinzukommen. Den habe ich im Wesentlichen in meinem Edge2 Array äh gespeichert. Den kann ich dann auch wieder auslesen rückwärts. Dann gibt's den auf jeden Fall. Und wenn es einen Weg gibt, dann werde ich auch irgendwann einen Weg zu diesem Knoten finden. Äh eine sauber sauberer Beweis würde eine Induktion machen über ähm die Zeit, die der Algorithmus da verbringt und über die ja über die Iteration des Algorithmus.

16:06 Äh für die Laufzeit ist ist wichtig, dass wir dieses markiert Array haben, damit wir einen Knoten nur einmal betreten. Dadurch ist klar, ich kann jeden Knoten einmal mit so einem rekursiven Aufruf versehen und innerhalb von diesem rekursiven Aufruf laufe ich einmal durch die ausgehenden Kanten. Die zeitliche Reihenfolge, wann ich das genau mache, ist ein bisschen weniger transparent. Ja, sehen Sie ja hier im Code. Ähm, ich habe dann immer diese anderen rekursiven Aufrufe zwischen geschaltet, bevor ich dann mit meinem Knoten der nächsten Kante weitermache. Aber über die Gesamtheit aller rekursiven Aufrufe hinweg habe ich eben für jeden Knoten einmal so ein Aufruf und in jedem Aufruf für jede ausgehende Kante einmal konstant viel Aufwand generiert. Damit habe ich insgesamt äh Linearzeit über die gesamten Aufrufe hinweg.

17:03 Es war nicht nur für den Beweis hilfreich, dass wir uns dieses Edge2 Array gemerkt haben, denn wir können nach so einer Tiefensuche auch äh für jeden anderen Knoten prüfen, ob er mit S verbunden ist. Na ja, das ist äh einfach, wenn er markiert ist, dann prüfe ich einfach ähm, ob das marked true ist. Und falls er aber verbunden ist, falls erreichbar ist, dann habe ich auch einen konkreten Weg zu diesem Knoten gefunden und den bekomme ich, indem ich dieses Edge to Array rückwärts laufe. Äh, der Code ist hier beschrieben. Ähm, sie erh sich, wir haben eine Klasse Depch, in der das dann gespeichert ist. Das heißt, diese ähm das Objekt von dieser Klasse hat dann eine Methode Path to und der kann ich einen anderen Knoten geben und der sofern der markiert ist, wenn es also keinen Pfad gibt, dann geht natürlich auch gibt's auch keinen Weg. Wenn der nicht erreichbar ist von S, dann gibt's keinen Weg. Aber wenn er erreichbar ist, dann habe ich letztlich hier nur eine Schleife rückwärts von Edge Tool zu verfolgen. Also ich starte mit meinem Knoten V.

18:09 Hier im Beispiel war der Startknoten hier die Null und wir sind hier lang gelaufen. Die fetten Kanten sind die, die in Edge2 gespeichert sind. Ähm und z.B. Zum Knoten 5 würde ich bei Knoten 5 starten und jeweils das Edge2 Array auslesen. Edge2 ist ja immer rückwärts diese Kante. Also Edge2 Eintrag bei 5 bringt mich zur 3 und da komme ich zur 2 und dann zur null und ich packe die auf einen Stack. Das heißt, die Ausgabe dreht den Pfad wieder um, denn ich habe den jetzt hier in umgekehrter Reihenfolge.

18:49 Und eigentlich sind die Kanten ja äh rückwärts. Ich habe den Pfad von null aus verfolgt, dann muss ich ihn auch von null aus wieder ausgeben.

19:05 Okay, ein Spar Spaßanwendung, was man mit Tiefensuchen noch so machen kann, äh sind z.B. alle möglichen äh Anwendung in der Bildverarbeitung. Äh sie kennen sich ja noch dieses äh Flatfill Oldschool ähm Bildverarbeitung, wo man die Sachen von Hand macht. äh kann man auf einen Pixel klicken und dann werden alle Pixel markiert oder eingefärbt, die die exakt gleiche Farbe haben oder die zumindest eine ähnliche Farbe haben. Das kann man realisieren über eine Tiefensuche, indem ich mir das Bild als einen Graf vorstelle, wo zwei Pixel verbunden sind, wenn sie benachbart sind und wenn der Farbwert ähnlich ist oder wenn der Farbwert gleich ist, je nachdem, wie sie wie sie die Operation definieren wollen. Und dann können sie weiß gar, ob man das hier gut sehen kann. Ähm, das soll das gleiche Bild sein, aber hier oben der Himmel ist mit ähm so einem Grau äh ersetzt. Hätte man vielleicht eine etwas etwas krasser rausstechende Farbe nehmen können.

20:09 Und sie können natürlich auch ihr Leben mit Tiefensuche planen. Äh, überlasse ich ihn, ob das eine gute Idee ist.