Algoritmos y Estructuras de Datos (VJ1215)

En la presentación del tema 6.3 (apartado 9.3.1 del libro "Data Structures and Algorithm Analysis in C++" (2014)) hemos visto que una de las aplicaciones importantes de la búsqueda en anchura es calcular la mínima cantidad de arcos necesaria para llegar desde un vértice origen hasta otro vértice o hasta todos los demás vértices. Eso es válido tanto con grafos dirigidos como con grafos no dirigidos. En el ejercicio 2.a has implementado una variante de eso que devuelve como resultado el árbol de caminos óptimos.

Para resolver el ejercicio 5, podemos modificar la búsqueda en anchura como sigue para no insertar en la cola los vértices que están a distancia puentes de islaJugador, puesto que a partir de ellos no hace falta seguir sumando enemigos (hay otras formas equivalentes de llegar al mismo resultado).

El coste temporal y espacial de este algoritmo es el propio de la búsqueda en anchura: O(|V| + |E|), gracias a la representación del grafo mediante listas de adyacencia.

int GrafoNoDirigido::contarEnemigosCercanos(int islaJugador,
                                            int puentes,
                                            const vector<int> & cantidadDeEnemigos) const {
   
   int resultado = cantidadDeEnemigos[islaJugador];

   vector<bool> visitado(vertices.size(), false);
   vector<int> distancia(vertices.size());
   queue<int> cola;

   distancia[islaJugador] = 0;
   visitado[islaJugador] = true;
   cola.push(islaJugador);

   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArco; arco != nullptr; arco = arco->siguiente)
	 if (! visitado[arco->vecino]) {
	    distancia[arco->vecino] = distancia[v] + 1;
	    visitado[arco->vecino] = true;
	    resultado += cantidadDeEnemigos[arco->vecino];
	    if (distancia[arco->vecino] < puentes)
	       cola.push(arco->vecino);
	 }
   }
   
   return resultado;

}
      

También nos podemos ahorrar el booleano visitado asociado a cada vértice, utilizando un valor especial de distancia para indicar que el vértice no está visitado:

int GrafoNoDirigido::contarEnemigosCercanos(int islaJugador,
                                            int puentes,
                                            const vector<int> & cantidadDeEnemigos) const {
   
   int resultado = cantidadDeEnemigos[islaJugador];

   vector<int> distancia(vertices.size(), -1);
   queue<int> cola;

   distancia[islaJugador] = 0;
   cola.push(islaJugador);

   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArco; arco != nullptr; arco = arco->siguiente)
	 if (distancia[arco->vecino] == -1) {
	    distancia[arco->vecino] = distancia[v] + 1;
	    resultado += cantidadDeEnemigos[arco->vecino];
	    if (distancia[arco->vecino] < puentes)
	       cola.push(arco->vecino);
	 }
   }

   return resultado;

}
      

En la siguiente solución, se añade a la anterior lo necesario para no seguir recorriendo innecesariamente el grafo si ya hemos llegado a todos los enemigos que hay:

int GrafoNoDirigido::contarEnemigosCercanos(int islaJugador,
					    int puentes,
					    const vector<int> & cantidadDeEnemigos) const {

   int cantidadDeEnemigosTotal = 0;
   for (int c : cantidadDeEnemigos)
      cantidadDeEnemigosTotal += c;
   
   int resultado = cantidadDeEnemigos[islaJugador];
   if (resultado == cantidadDeEnemigosTotal)
      return resultado;
   
   vector<int> distancia(vertices.size(), -1);
   queue<int> cola;

   distancia[islaJugador] = 0;
   cola.push(islaJugador);

   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArco; arco != nullptr; arco = arco->siguiente)
	 if (distancia[arco->vecino] == -1) {
	    distancia[arco->vecino] = distancia[v] + 1;
	    resultado += cantidadDeEnemigos[arco->vecino];
	    if (resultado == cantidadDeEnemigosTotal)
	       return resultado;
	    if (distancia[arco->vecino] < puentes)
	       cola.push(arco->vecino);
	 }
   }

   return resultado;

}