Grafos - Algoritmo basico de busqueda BFS (Parte 3.1)


  • 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 articulo explicaremos la búsqueda por anchura (BFS).

    A continuación se muestra el algoritmo de la búsqueda por anchura en un grafo representado por medio de listas de adyacencias. En dicho algoritmo se usa una cola para almacenar los nodos adyacentes al actual y guardarlos para continuar con la búsqueda. La siguiente implementación del recorrido por anchura para un grafo completamente conectado (existe al menos un camino entre cualquier par de vértices en el grafo) y para un grafo que no lo esta.

    int visitado[1000];
    vector<list<int> > grafo(1000);
    
    // algoritmo para grafo completamente conectado
    void BFS(int v) { // v es el nodo de inicio del recorrido
      list<int> cola; // cola de adyacentes
      list<int>::iterator nodo_actual, aux, fin;
      visitado[v] = 1; // marcamos como visitado el nodo de inicio
      cola.push_back(v); // metemos inicio a la cola
      while (!cola.empty()) {
        nodo_actual = cola.front(); // sacar nodo de la cola
        cola.pop_front();
        aux = grafo[nodo_actual].begin(); //posicionar iteradores para
                                          //lista de ady
        fin = grafo[nodo_actual].end();
        while (aux != fin) {      // recorrer todos los nodos ady a nodo actual
          if (!visitado[*aux]) {  // añadir a la cola solo los no visitados
            visitado[*aux] = 1;   // marcarlos como visitados
            cola.push_back(*aux); // añadirlos a la cola
            // aqui podriamos añadir codigo para hacer algo mientras
            // recorremos el grafo
          }
          aux++; // avanzar al siguiente adyacente del nodo actual
        }	   
      }
    }
    
    // algoritmo para grafo que no esta completamente conectado
    void BFS2() {
      for (int i = 0; i < nvert; i++)
        if (!visitado[i])
          BFS(i);
    }
    

    En esta implementación podrán ver que primero se visitan los nodos o vértices que fueron visitados primero.

    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 BFS(0)
        nodoActual = -1, cola = [0]
    1. Sacamos el primer nodo de la cola
        nodoActual = 0, cola = []
    2. 0 visitara a BFS(1) y BFS(3)
        nodoActual = 0, cola = [1, 3]
    3. Sacamos el primer nodo de la cola
        nodoActual = 1, cola = [3]
    4. 1 visitara a BFS(2) y BFS(3) pero 3 ya fue visitado
        nodoActual = 1, cola = [3, 2]
    5. Sacamos el primer nodo de la cola
        nodoActual = 3, cola = [2]
    6. 3 visitara a BFS(2) y BFS(4) pero 2 ya fue visitado
        nodoActual = 3, cola = [2, 4]
    7. Sacamos el primer nodo de la cola
        nodoActual = 2, cola = [4]
    8. 2 visitara a BFS(4) pero 4 ya fue visitado
        nodoActual = 2, cola = [4]
    9. Sacamos el primer nodo de la cola
        nodoActual = 4, cola = []
    10. El algoritmo termina por la cola esta vacía
    

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