Depth-first search

Pseudocode

DFS(G)

1. for each vertex u ∈ V [G]
   
2. do color[u] ← WHITE
   

3
4
5
6

DFS(G)
1   '''for''' each v of G {        // Alle Knoten weiß färben, Vorgänger auf nil setzen
2      col[v] = 'w';
3      pi[v] = nil;
4   }
5   time = 0;
6   for each u of G          // Für alle weißen Knoten: DFS-visit aufrufen
7      if col[u] == 'w'
8         DFS-visit(u);

DFS-visit(u)
1   col[u] = 'g';            // Aktuellen Knoten grau färben
2   time++;                  // Zeitzähler erhöhen
3   d[u] = time;             // Entdeckzeit des aktuellen Knotens setzen
4   for each v of Adj[u] {   // Für alle weißen Nachbarn des aktuellen Knotens
5       if col[v] == 'w' {
6          pi[v] = u;         // Vorgänger auf aktuellen Knoten setzen
7          DFS-visit(v);      // DFS-visit aufrufen
8       }
9    }
10   col[u] = 's';           // Aktuellen Knoten schwarz färben
11   time++;
12   f[u] = time;            // Finishing-Time des aktuellen Knotens setzen