Grundproblem der Tiefensuche:
Wir wollen einen Algorithmus entwickeln, der für beliebige Knotenpaare A, B in einem Graphen ermitteln kann, ob diese beiden Knoten durch einen Pfad verbunden sind.

Sehen Sie sich zunächst das folgende Video an, in dem der Algorithmus der Tiefensuche erklärt wird:

Im Video verwendete Fachwörter:

• vertex (auch: node) → Knoten
• edge → Kante
• DFS: Depth first search → Tiefensuche
• graph traversal → Traversierung eines Graphen (d.h. Beschreitung all seiner Knoten)

Informelle Beschreibung des Algorithmus: Wir entwickeln eine Methode istVerbundenRekursiv(int startknoten, int zielknoten), die genau dann true zurückliefert, wenn es einen Pfad vom Startknoten zum Zielknoten gibt. Sie geht dazu folgendermaßen 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.

Problem:
Dieses Vorgehen kann bei zyklischen Graphen zu einer unendlichen Methodenaufrufkette führen.

Lösung:
Der Algorithmus muss speichern, welche Knoten er schon besucht hat und diese bei Schritt 2.) auslassen. 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 zu Beginn des Algorithmus (im Programm unten in der Methode istVerbunden) instanziert und mit false-Werten befüllt.
In Schritt 1.) wird schonBesucht[startknoten] = true gesetzt und bei 2.) wird eine Referenz auf das Array schonBesucht bei jedem weiteren Aufruf von istVerbundenRekursiv weitergereicht.

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 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 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.