Algoritmos y Estructuras de Datos (VJ1215)

En este ejercicio podemos aplicar un razonamiento que hemos visto en el ejercicio 3.c del tema 6: movernos utilizando arcos de entrada.

El problema se resuelve eficientemente haciendo una búsqueda en anchura desde el vértice t que recorra los arcos de entrada, y añadiendo los jugadores al resultado en el orden en que los vamos encontrando en esa búsqueda. De ese modo, quedan ordenados de menor a mayor distancia a t.

El coste temporal y espacial de este algoritmo es O(n + |V| + |E|) gracias a que trabajamos con una representación del grafo mediante listas de adyacencia.

void GrafoDirigido::rankingPorDistanciaAlObjetivo(int t, vector<int> & jugadores) const {

   // Empezamos asociando a cada vertice un contador con la cantidad de jugadores en ese vertice

   vector<int> jugadoresEnVertice(vertices.size(), 0);

   for (int v : jugadores)
      jugadoresEnVertice[v]++;

   // Tratamos el caso especial de que haya jugadores en el vertice t

   int contador = 0;
   for (int i = jugadoresEnVertice[t]; i > 0; i--)
      jugadores[contador++] = t;
   if (contador == jugadores.size())
      return;

   // Realizamos una busqueda en anchura desde t siguiendo los arcos de entrada,
   // y ponemos los jugadores en el resultado en el orden en que los vamos encontrando

   vector<bool> visitado(vertices.size(), false);
   queue<int> cola;
   visitado[t] = true;
   cola.push(t);

   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente)
	 if (! visitado[arco->vecino]) {
	    for (int i = jugadoresEnVertice[arco->vecino]; i > 0; i--)
	       jugadores[contador++] = arco->vecino;
	    if (contador == jugadores.size())
	       return;
	    visitado[arco->vecino] = true;
	    cola.push(arco->vecino);
	 }
   }


   // Tratamos el caso especial de que haya jugadores para los que t es inalcanzable
   
   for (int v = 0; v < vertices.size(); v++)
      if (! visitado[v]) {
         for (int i = jugadoresEnVertice[v]; i > 0; i--)
            jugadores[contador++] = v;
         if (contador == jugadores.size())
            return;
      
      }
   
}