Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 21.b del tema 6

En este ejercicio podemos aplicar de nuevo un razonamiento que hemos visto en el ejercicio 3.c.

La solución eficiente consiste en hacer una búsqueda en anchura o en profundidad desde q en el grafo invertido, que es lo mismo que hacer una búsqueda desde q recorriendo los arcos de entrada, y terminar cuando todos los vértices con ratón son visitados o cuando no hay más vértices alcanzables desde q en el grafo invertido. El coste temporal es O(|V| + |E|) con una representación del grafo que incluya listas de arcos de entrada.

Solución 1 (en anchura)

bool GrafoConEnlaces::quesoAlcanzablePorTodosLosRatones(int queso,
							const vector<bool> & raton) const {

   int cantidadDeVertices = vertices.size();
   
   vector<bool> visitado(cantidadDeVertices, false);
   queue<int> cola;
 
   int cantidadDeRatonesPorVisitar = 0;

   for (int v = 0; v < cantidadDeVertices; v++)
      if (raton[v])
	 cantidadDeRatonesPorVisitar++;
   
   if (cantidadDeRatonesPorVisitar == 0)
      throw string("Faltan los ratones");

   if (raton[queso] && --cantidadDeRatonesPorVisitar == 0)
       return true;
   visitado[queso] = true;
   cola.push(queso);

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

   return false;

}

Solución 2 (en profundidad)

bool GrafoConEnlaces::buscarRatonesDFS(int v,
				       const vector<bool> & raton,
				       int & cantidadDeRatonesPorVisitar,
				       vector<bool> & visitado) const {
   
   if (raton[v] && --cantidadDeRatonesPorVisitar == 0)
	 return true;

   visitado[v] = true;

   for (Arco * arco = vertices[v].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente)
      if (! visitado[arco->vecino])
	 if (buscarRatonesDFS(arco->vecino, raton, cantidadDeRatonesPorVisitar, visitado))
	    return true;

   return false;

}


bool GrafoConEnlaces::quesoAlcanzablePorTodosLosRatones(int queso,
							const vector<bool> & raton) const {

   int cantidadDeVertices = vertices.size();

   vector<bool> visitado(cantidadDeVertices, false);
 
   int cantidadDeRatonesPorVisitar = 0;

   for (int v = 0; v < cantidadDeVertices; v++)
      if (raton[v])
	 cantidadDeRatonesPorVisitar++;
   
   if (cantidadDeRatonesPorVisitar == 0)
      throw string("Faltan los ratones");

   return buscarRatonesDFS(queso, raton, cantidadDeRatonesPorVisitar, visitado);

}