Saltar la navegación

Algoritmo en pseudocódigo

Se plantea el algoritmo siguiendo un esquema recursivo:

dado G = (V , E)

1. Marcar todos los vértices como no visitados.
2. Elegir vértice u como punto de partida.
3. Marcar u como visitado.
4. Para todo v adyacente a u,(u,v) Є E, si v no ha sido visitado, llamar recursivamente para ejecutar (3) y (4) para v.

Finalizar cuando se hayan visitado todos los nodos alcanzables desde u.

Si desde u no fueran alcanzables todos los nodos del grafo: volver a (2), elegir un nuevo vértice de partida v no visitado, y repetir el proceso hasta que se hayan recorrido todos los vértices.

Escrito en pseudocódigo:

 main_dfs (grafo)
inicializar marca en false (arreglo de booleanos);
para cada vértice v del grafo
       si (marca[v] == noVisitado) -> dfs(v);
          
dfs (v: vértice)
  marca[v]:= visitado;
  para cada nodo w adyacente a v
         si (marca[w] == noVisitado) -> dfs(w);