Depth-first search

Pseudocode

DFS(G)

1. for each vertex u ∈ V [G]
   

1. do color[u] ← WHITE
   

3
4
5
6

DFS(G)
1   <b>for</b> each vertex of [<i>G</i>]         /2      col[v] = 'w';
3         do <i>color</i>[<i>u</i>] ← WHITE
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