Dies ist eine alte Version des Dokuments!
Tiefensuche (für interessierte Schüler/innen)
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", gibtruezurück. - 2.) Überprüfe für jeden von
startknotenaus erreichbaren Knoteni, obistVerbundenRekursiv(i, zielknoten) == trueist. Falls "ja", gibtruezurü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 Methode folgt einem uninformierten Suchverfahren (uninformiert bedeutet hier, dass dem Verfahren über die Einträge der Adjazenzmatrix hinaus keine weiteren Informationen zur Verfügung stehen) mit dem Namen 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 den entsprechenden Artikel in Wikipedia, der auch eine schöne Animation dazu zeigt).
Ein zweites uninformiertes 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 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.
Wir entwickeln eine Klasse Graph, die nützliche Methoden zur Verwaltung und Analyse von Graphen bereitstellt.
Den im Testprogramm unten generierten Graphen siehst Du in graphischer Darstellung links neben dem Programmkasten. So kannst Du das Programm schrittweise ausführen und gleichzeitig den Programmverlauf am Graphen mitverfolgen.
Aufgaben:
- Erstelle eine Methode
void adjazenzmatrixAusgaben(), die die Adjazenzmatrix folgendermaßen auf dem Bildschirm ausgibt:
0 1 0 1 0 1 0 1 0
- Erstelle eine Methode
istIsoliert(int knoten), die genau danntruezurückgibt, wenn der Knoten isoliert ist (Definition siehe oben).