Algoritmos y Estructuras de Datos (VJ1215)

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 {
   
   vector<bool> visitado(vertices.size(), false);
   vector<int> distancia(vertices.size());
   queue<int> cola;

   distancia[islaJugador] = 0;
   visitado[islaJugador] = true;
   cola.push(islaJugador);
   int resultado = cantidadDeEnemigos[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 {
   
   vector<int> distancia(vertices.size(), -1);
   queue<int> cola;

   distancia[islaJugador] = 0;
   cola.push(islaJugador);
   int resultado = cantidadDeEnemigos[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;

}