Depth-first search: Difference between revisions

Revision as of 16:46, 14 August 2014

3
4
5
6

@@ Line 13: / Line 13: @@
 <br/>
 <br/>
-<pre>
-DFS(G)
-   <b>for</b> each vertex of [<i>G</i>]         /2      col[v] = 'w';
-         do <i>color</i>[<i>u</i>] &larr; WHITE
-   }
-   time = 0;
-   for each u of G          // Für alle weißen Knoten: DFS-visit aufrufen
-      if col[u] == 'w'
-         DFS-visit(u);
-</pre>
-<pre>
-DFS-visit(u)
-   col[u] = 'g';            // Aktuellen Knoten grau färben
-   time++;                  // Zeitzähler erhöhen
-   d[u] = time;             // Entdeckzeit des aktuellen Knotens setzen
-   for each v of Adj[u] {   // Für alle weißen Nachbarn des aktuellen Knotens
-       if col[v] == 'w' {
-          pi[v] = u;         // Vorgänger auf aktuellen Knoten setzen
-          DFS-visit(v);      // DFS-visit aufrufen
-       }
-    }
-   col[u] = 's';           // Aktuellen Knoten schwarz färben
-   time++;
-   f[u] = time;            // Finishing-Time des aktuellen Knotens setzen
-</pre>