Algoritmos y Estructuras de Datos (VJ1215)

void GrafoDirigido::mostrarOrdenTopologico() const {
  
   cout << "Ordenacion topologica:" << endl;
   
   vector<int> entradasRestantes(vertices.size());
   vector<int> ordenTopologico(vertices.size());
   queue<int> cajaDeVerticesConCeroEntradasRestantes; // En este algoritmo tambien se podria usar stack
   int contadorDeVertices = 0;
  
   for (int v = 0; v < vertices.size(); v++) {
      entradasRestantes[v] = vertices[v].gradoDeEntrada;
      if (entradasRestantes[v] == 0)
	 cajaDeVerticesConCeroEntradasRestantes.push(v);
   }

   while (! cajaDeVerticesConCeroEntradasRestantes.empty()) {
      int v = cajaDeVerticesConCeroEntradasRestantes.front();
      cajaDeVerticesConCeroEntradasRestantes.pop();
      ordenTopologico[contadorDeVertices++] = v;
      for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente)
	 if (--entradasRestantes[arco->vecino] == 0)
	    cajaDeVerticesConCeroEntradasRestantes.push(arco->vecino);
   }
  
   if (contadorDeVertices != vertices.size())
      throw string ("ERROR: el grafo no es aciclico");

   for (int v : ordenTopologico)
      cout << v << endl;

}