Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2024/2025

Ejemplo de error en el ejercicio 5 del tema 6

La siguiente solución no es correcta, piensa por qué.

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;
   int distancia = 0;

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

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

}
      

¿Por qué es incorrecta?

El cálculo de distancia es incorrecto, la distancia a la que están los vértices no aumenta en 1 de esa manera cada vez que sale uno de la cola.