Curso 2024/2025
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; }