Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 7 del tema 6

Se muestran a continuación dos soluciones basadas en el algoritmo de Kahn.

Nos dicen que el grafo es acíclico, por lo que no hace falta comprobar eso.

El coste temporal y espacial de ambas soluciones es el del algoritmo de Kahn: O(|V| + |E|).

Solución 1

Una forma de resolver este ejercicio es partir del algoritmo de Kahn y añadir dos contadores anyos y simultaneas como se muestra a continuación.

int GrafoDirigido::minimaCantidadAnyos() const {

   vector<int> entradasRestantes(vertices.size());
   queue<int> cajaDeVerticesConCeroEntradasRestantes;
  
   for (int v = 0; v < vertices.size(); v++) {
      entradasRestantes[v] = vertices[v].gradoDeEntrada;
      if (entradasRestantes[v] == 0)
	 cajaDeVerticesConCeroEntradasRestantes.push(v);
   }

   int anyos = 0;
   int simultaneas = cajaDeVerticesConCeroEntradasRestantes.size();

   while (! cajaDeVerticesConCeroEntradasRestantes.empty()) {
      int v = cajaDeVerticesConCeroEntradasRestantes.front();
      cajaDeVerticesConCeroEntradasRestantes.pop();
      cout << "Asignatura " << v << ":\tanyo " << anyos + 1 << endl;

      for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente)
	 if (--entradasRestantes[arco->vecino] == 0)
	    cajaDeVerticesConCeroEntradasRestantes.push(arco->vecino);

      if (--simultaneas == 0) {
	 anyos++;
	 simultaneas = cajaDeVerticesConCeroEntradasRestantes.size();
      }
   }
  
   return anyos;

}

Solución 2

Otra forma de resolver este ejercicio es partir del algoritmo de Kahn y añadir el vector anyo como se muestra a continuación.

int GrafoDirigido::minimaCantidadAnyos() const {

   vector<int> entradasRestantes(vertices.size());
   vector<int> anyo(vertices.size());
   queue<int> cajaDeVerticesConCeroEntradasRestantes;
   int v;
  
   for (v = 0; v < vertices.size(); v++) {
      entradasRestantes[v] = vertices[v].gradoDeEntrada;
      if (entradasRestantes[v] == 0) {
	 cajaDeVerticesConCeroEntradasRestantes.push(v);
	 anyo[v] = 1;
      }
   }

   while (! cajaDeVerticesConCeroEntradasRestantes.empty()) {
      v = cajaDeVerticesConCeroEntradasRestantes.front();
      cajaDeVerticesConCeroEntradasRestantes.pop();
      cout << "Asignatura " << v << ":\tanyo " << anyo[v] << endl;

      for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente)
	 if (--entradasRestantes[arco->vecino] == 0) {
	    cajaDeVerticesConCeroEntradasRestantes.push(arco->vecino);
	    anyo[arco->vecino] = anyo[v] + 1;
	 }

   }
  
   return anyo[v]; // Es el ultimo v del bucle anterior

}