Basierend auf meinem letzten Beitrag habe ich jetzt noch die Tiefensuche mit Hilfe einer Adjazenzmatrix implementiert. Besuchte Knoten werden mit Gelb markiert und der aufspannenden Baum besteht aus gelben Kanten.

Die Knoten 1 und 7 wurden nicht besucht, was man an dem fehlenden gelben Punkt sieht. Ob ein Graph zusammenhängend ist, lässt sich daher mit der Tiefesuche feststellen.

Zum besseren Verständnis habe ich noch das in meinem Fall benötigte besucht[]:boolean – Feld ausgeben lassen, sowie den zu jedem Knoten gehörigen Vorgänger-Knoten, den ich in einem Feld vorgaenger[]:int speichere.

Die darüberstehenden Zahlen gibt die Durchlaufreihenfolge der Knoten wieder.

Den bisherigen Stand biete ich hier wieder zum Download an: ProcessingTiefensuche

Im nächsten Schritt möchte ich natürlich den schrittweisen Durchlauf animiert darstellen. Aber dazu muss ich die rekursive Implementierung des Algorithmus aufbrechen, damit bei jedem Durchlauf der draw()-Methode nur 1 Schritt gemacht wird.