Algoritmos y Estructuras de Datos (VJ1215)

El algoritmo de Kahn resuelve también el problema de averiguar si hay ciclos, como hemos visto en el ejercicio 4. El coste temporal y espacial de este algoritmo es O(|V| + |E|) con una representación del grafo mediante listas de adyacencia.

Si el único resultado que nos interesa es ese, quedaría así:

bool GrafoDirigido::esAciclico() const {
  
   vector<int> entradasRestantes(vertices.size());
   queue<int> caja;
   int contadorDeVertices = 0;
  
   for (int v = 0; v < vertices.size(); v++) {
      entradasRestantes[v] = vertices[v].gradoDeEntrada;
      if (entradasRestantes[v] == 0)
         caja.push(v);
   }

   while (! caja.empty()) {
      int v = caja.front();
      caja.pop();
      contadorDeVertices++;
      for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente)
         if (--entradasRestantes[arco->vecino] == 0)
            caja.push(arco->vecino);
   }
  
   return contadorDeVertices == vertices.size();
}