Tarjan steht im D-Book für die Vertiefung der Graphtraversierung. In Q1.5 lernen Schülerinnen und Schüler Graphen zunächst als Modelle aus Knoten und Kanten kennen. BFS zeigt, wie man von einem Startknoten aus Ebenen bildet und in ungewichteten Graphen kürzeste Wege nach Kantenzahl findet. DFS ergänzt diese Perspektive grundlegend anders: Es geht möglichst weit in die Tiefe, bevor Alternativen verfolgt werden.
Didaktisch ist DFS besonders interessant, weil der Rücksprung Teil der Struktur wird. Ein rekursiver Aufruf oder ein Stack merkt, wo die Suche fortgesetzt werden kann. Dadurch verbindet DFS Q1.5 mit Q1.3: Rekursion und Backtracking werden nun auf Graphen angewendet. Gleichzeitig verbindet DFS Q1.5 mit Q1.4, weil Stack, Markierung und Adjazenzstruktur zusammenspielen.
Tarjans Bedeutung liegt darin, DFS als Werkzeug für lineare Graphalgorithmen sichtbar zu machen. Der Suchbaum, die Entdeckungsordnung und Rückverbindungen können genutzt werden, um stärkere Aussagen über den Graphen zu gewinnen. Im Unterricht muss das nicht bis zur vollständigen Theorie starker Zusammenhangskomponenten ausgebaut werden. Wichtig ist: Traversierung erzeugt verwertbare Strukturinformation.
Damit wird DFS nicht auf „besuche alle Knoten“ reduziert. Es ist ein Verfahren, mit dem Graphen systematisch erschlossen werden. Q1.5 gewinnt dadurch eine zweite algorithmische Achse neben BFS.
Im D-Book ist Tarjan deshalb der DFS-Tiefenanker: Euler modelliert Beziehungen, Moore/BFS erschließt Ebenen und kürzeste Wege, Tarjan/DFS erschließt Tiefe, Rücksprung und Struktur.
