Algoritmos y Estructuras de Datos (VJ1215)

La búsqueda en anchura se puede adaptar fácilmente para averiguar si un vértice t es alcanzable desde un vértice s, basta con añadir esto a una búsqueda en anchura que parta desde s:

• Antes de insertar un vértice en la cola, si es t terminamos devolviendo cierto.

• Tras vaciarse la cola, terminamos devolviendo falso.

El coste temporal y espacial de este algoritmo es O(|V| + |E|) con una representación del grafo mediante listas de adyacencia.

bool GrafoDirigido::esAlcanzable(int origen, int destino) const {

   if (origen == destino)
      return true;
   
   queue<int> cola;
   vector<bool> visitado(vertices.size(), false);

   visitado[origen] = true;
   cola.push(origen);

   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente)
         if (! visitado[arco->vecino]) {
            if (arco->vecino == destino)
               return true;
            visitado[arco->vecino] = true;
            cola.push(arco->vecino);
         }
   }

   return false;

}