|
|
| Line 13: |
Line 13: |
| 5<br/> | | 5<br/> |
| 6<br/> | | 6<br/> |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
| <pre>
| |
| 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);
| |
| </pre>
| |
| <pre>
| |
| 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
| |
| </pre>
| |