Tiefensuche (rekursiv)

• Eingabe: ein gerichteter Graph G = (V, E)
• Ausgabe: eine Knotenreihenfolge b : V$\to$$\mathbb {N}$

for ( Knoten x in V ) { besucht[x] = false; }
int counter = 0;
while ( exists x : not besucht[x] ) { dfs (x); }

dfs (x) {
  // zu x existiert Weg aus Baumkanten
  besucht[x] = true; b[x] = ++counter;
  for ( y in Nachbarn von x ) {
    if ( not besucht[y]  ) {
      dfs (y); // xy heißt Baum-Kante
} } }