Recorridos sobre grafos
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);
Obra publicada con Licencia Creative Commons Reconocimiento Compartir igual 4.0