===== Tiefensuche (für interessierte Schüler/innen) ===== Die Behandlung der Tiefensuche ist **im Lehrplan leider nicht vorgesehen**. Weil dieser Algorithmus sich sehr gut eignet, um einen Einblick in die Programmierung mithilfe von rekursiven Methodenaufrufen zu bekommen, finden interessierte Schüler/innen hier eine Einführung zum Selbststudium. Falls Sie Fragen dazu haben, stehe ich gerne zur Verfügung! {{ youtube>PMMc4VsIacU?large }} Wir wollen eine Methode ''istVerbundenRekursiv(int startknoten, int zielknoten)'' schreiben, die genau dann ''true'' zurückliefert, wenn es einen Pfad vom Startknoten zum Zielknoten gibt. Wir gehen nach folgender Strategie vor: * 1.) Überprüfe, ob ''startknoten == zielknoten''. Falls "ja", gib ''true'' zurück. * 2.) Überprüfe für jeden von ''startknoten'' aus erreichbaren Knoten ''i'', ob ''istVerbundenRekursiv(i, zielknoten) == true'' ist. Falls "ja", gib ''true'' zurück. Dieses Vorgehen kann bei zyklischen Graphen zu einer **unendlichen Methodenaufrufkette** führen. Daher muss der Algorithmus **speichern, welche Knoten er schon besucht hat** und diese bei 2.) ausnehmen. Dies geschieht mittels eines Arrays ''boolean[] schonBesucht'', das für jeden Knoten einen booleschen Wert speichert, der angibt, ob der Knoten schon besucht wurde. Dieses Array wird anfangs in der Methode ''istVerbunden'' instanziert und mit ''false''-Werten befüllt. Diese übergibt die Refernz auf dieses Array an die Methode ''istVerbundenRekursiv''. Bei 1.) wird ''schonBesucht[startknoten] = true'' gesetzt und bei 2.) wird eine Referenz auf das Array ''schonBesucht'' bei jedem weiteren Aufruf von ''istVerbundenRekursiv'' weitergereicht. \\ \\ Die fertigen Methoden ''istVerbunden'' und ''istVerbundenRekursiv'' sind im obigen Programm schon eingebaut. Der Graph, der im Hauptprogramm aufgebaut wird, ist rechts dargestellt. Die beschriebene Methode nennt man **Tiefensuche** (engl. depth-first search, DFS). "Bei der Tiefensuche wird zunächst jeder Pfad vollständig in die Tiefe beschritten, bevor abzweigende Pfade beschritten werden." (siehe [[https://de.wikipedia.org/wiki/Tiefensuche|den entsprechenden Artikel in Wikipedia, der auch eine schöne Animation dazu zeigt)]]. \\ \\ Ein zweites Suchverfahren wäre die **Breitensuche** (engl. breadth-first search, BFS). Bei dieser werden "zunächst alle Knoten beschritten, die vom Ausgangsknoten direkt erreichbar sind. Erst danach werden Folgeknoten beschritten." (siehe [[https://de.wikipedia.org/wiki/Breitensuche|den entsprechenden Artikel in Wikipedia, und die sehr anschauliche Animation dort.)]] \\ \\ Keines der beiden Suchverfahren ist für das allgemeine Problem der Suche in Graphen „besser“ geeignet als das andere. {{ :graphen:20211107-152623.png?200|}} Den im Testprogramm unten generierten Graphen siehst Du in graphischer Darstellung im Bild rechts. So kannst Du das Programm schrittweise ausführen und gleichzeitig den Programmverlauf am Graphen mitverfolgen.

**Aufgabe (nicht leicht...):** \\ \\ Erweitere das Programm so, dass die Methoden ''istVerbunden'' in dem Fall, dass sie einen Pfad gefunden hat, diesen in der Form 7->0->1->2->3->4 ausgibt. \\ \\ [[.istverbundenaufgabe:loesung|Lösung]]