Ernesto Carrión

Ahora que ya sabemos como representar grafos, probablemente lo que queramos hacer es recorerlos.

Una de las formas más básicas de recorrer un grafo es el DFS (Depth First Search) que se traduce como Búsqueda en Profundidad; y básicamente  eso es lo que hace, dado un grafo, parte de un nodo inicial y lo recorre de la siguiente manera:

1. Visita el nodo inicial.
2. Visita su primer nodo adyacente (Nodo conectado a el).
3. Visita el primer nodo adyacente del nuevo nodo.
4. Repite el proceso hasta que ya no tenga mas nodos que visitar (llego a una hoja o el nodo que sigue ya esta visitado);
5. Cuando llega al paso anterior, se devuelve (Backtracking) hasta el primer lugar en el grafo donde queden nodos por visitar.

Una vez el DFS termina su recorrido, este grafo se convierte en un árbol.

El DFS  logra su recorrido con una pila, cada nodo nuevo que se valla visitando se va metiendo a la pila, cuando llega la hora de hacer el backtracking sacamos de la pila y repetimos el procedimiento. Por suerte la recursión hace todo este trabajo y nos evita el uso de la pila.

A continuación, mi pequeña implementación recursiva del DFS en C++.

void dfs(vector<int> * g, bool * visited, int start){

  //Acabamos de visitar un nodo, asi que lo tachamos
  visited[start] = true;
  cout << "Nodo " << start << " visitado" << endl;

  //Para Cada Nodo visitamos sus adyacentes
  //Osea a los que este puede ir
  for(int i = 0; i < g[start].size(); i++){

    //Si el nodo no ha sido visitado todavia
    //Le aplicamos nuevamente el mismo procedimiento
    if(!visited[g[start][i]]){
      dfs(g, visited, g[start][i]);
    }
  }

}

PD: Para que el DFS funcione correctamente el grafo debe ser conexo, es decir cada nodo debe estar conectado con otro, lo que significa que siempre debe haber un camino de un nodo a otro, cualquiera que sea.