Grafos - Algoritmo básico de búsqueda DFS (Parte 3.2)


  • administrators

    Existen dos algoritmos básicos para recorrer un grafo o buscar un nodo en particular, la búsqueda por anchura o BFS y la búsqueda por profundidad o DFS. En este artículo explicaremos la búsqueda por profundidad (DFS).

    El algoritmo de la búsqueda por profundidad se puede hacer modificando el anterior (Parte 3.1 BFS) en la parte que usa una cola y usar una pila. Otra forma de implementarla es usando recursividad, a continuación se muestran ambos enfoques así como la rutina para hacer la búsqueda en grafos que no están completamente conectados.

    A continuación se presenta el listado con la implementación de la búsqueda por profundidad o DFS. También se ha añadido en la versión recursiva un contador que marca el orden en el que fueron visitados los nodos del grafo, dicho orden es muy útil al implementar otros algoritmos de grafos.

    Implementación DFS (usando una pila)

    int visitado[1000];
    vector<list<int> > grafo(1000);
    
    void DFS(int v) { //v es el nodo de inicio del recorrido
      list<int> pila; //pila de nodos adyacentes
      list<int>::iterator nodo_actual, aux, fin;
      visitado[v] = 1; //marcar como visitado el nodo de inicio
      pila.push_back(v);
      while (!pila.empty()) { //mientras no se vacie la pila de adyacentes
        nodo_actual = pila.back();
        //aqui podriamos marcar el orden en que se visitaron
        pila.pop_back();
        aux = grafo[nodo_actual].begin(); // posicionar iteradores para
                                          // lista adyacente
        fin = grafo[nodo_actual].end();
        while (aux != fin) { //recorrer todos los adyacente al nodo actual
          if (!visitado[*aux]) { //añadir a la pila solo los no visitados
            visitado[*aux] = 1;
            pila.push_back(*aux);
            //aqui podemos añadir código para hacer algo mientras
            //realizamos el recorrido
          }
          aux++; //avanzar al siguiente adyacente del nodo actual
        }
      }
    }
    

    Implementacion DFS (recursiva)

    int visitado[1000];
    vector<list<int> > grafo(1000);
    
    void DFS(int v) {
      list<int>::iterator aux, fin; //iteradores para lista de ady
      visitado[v] = 1; //marcar como visitado
      //aqui se podria marcar el orden en que fueron visitados
      aux = grafo[v].begin(); //posicionar los iteradores para lista de ady
      fin = grafo[v].end();
      while (aux != fin) {
        if (!visitado[*aux])
          DFS(*aux); //no se necesita marcar porque *aux se convierte en v
        aux++; //avanzar al siguiente adyacente de v
      }
    }
    
    //esta es la version para grafos que no estan completamente conectados
    void DFS2() {
      int i;
      for (int i = 0; i < nvert; i++) //buscar un nuevo nodo de
        if  (!visitado[i])            //inicio que no ha sido visitado
          DFS(i);
    }
    

    En esta implementación podrán ver que primero se visitan los nodos o vértices que fueron visitados al final, en este caso los números que se encuentran en la pila tienen como primer número al último que fue ingresado.

    0_1537932896697_thomas miller (2).png

    Por ejemplo para el grafo de la figura si comenzamos la búsqueda por el nodo cero (0).

    0. Inicio DFS(0)
        nodoActual = -1, pila = [0]
    1. Sacamos el primer nodo de la pila
        nodoActual = 0, pila = []
    2. 0 visitara a DFS(1) y DFS(3)
        nodoActual = 0, pila = [1, 3]
    3. Sacamos el primer nodo de la pila
        nodoActual = 3, pila = [1]
    4. 3 visitara a DFS(2) y DFS(4)
        nodoActual = 3, pila = [1, 2, 4]
    5. Sacamos el primer nodo de la pila
        nodoActual = 4, pila = [1, 2]
    6. 4 no visita a ningun nodo
        nodoActual = 4, pila = [1, 2]
    7. Sacamos el primer nodo de la pila
        nodoActual = 2, pila = [1]
    8. 2 visitara a DFS(4) pero 4 ya fue visitado
        nodoActual = 2, pila = [1]
    9. Sacamos el primer nodo de la pila
        nodoActual = 1, pila = []
    10. El algoritmo termina por la pila esta vacía
    

    En el caso de la implementación recursiva deberán hacerla correr con un ejemplo de grafo para poder analizar la pila, cuando las funciones se llaman recursivamente verán que no se llama a una sin que termine la última en ser llamada y a su vez esperará hasta que todas las funciones llamadas por la otra función sean terminadas.

    #include <iostream>
    #include <vector>
    #include <list>
    using namespace std;
    
    int visitado[1000];
    vector<list<int> > grafo(1000);
    
    void DFS(int v) {
      list<int>::iterator aux, fin; //iteradores para lista de ady
      visitado[v] = 1; //marcar como visitado
      //aqui se podria marcar el orden en que fueron visitados
      cout << v << " fue visitado" << endl;
      aux = grafo[v].begin(); //posicionar los iteradores para lista de ady
      fin = grafo[v].end();
      while (aux != fin) { // este ciclo extra esta para imprimir los siguientes nodos
        cout << '\t' << (*aux) << " sera visitado por " << v << endl;
        aux++; //avanzar al siguiente adyacente de v
      }
      aux = grafo[v].begin(); //posicionar los iteradores para lista de ady
      fin = grafo[v].end();
      while (aux != fin) {
        if (!visitado[*aux])
          DFS(*aux); //no se necesita marcar porque *aux se convierte en v
        aux++; //avanzar al siguiente adyacente de v
      }
    }
    
    int main() {
      // conectamos el grafo
      grafo[0].push_back(1);
      grafo[0].push_back(3);
      grafo[1].push_back(2);
      grafo[1].push_back(3);
      grafo[2].push_back(4);
      grafo[3].push_back(2);
      grafo[3].push_back(4);
      // llamamos a la funcion DFS
      DFS(0);
    }
    

    Para practicar con este tipo de busqueda puedes utlizar uno de los siguientes enlaces: