Algoritmos y Estructuras de Datos (VJ1215)

Si el vértice w es alcanzable desde el vértice v, entonces solo puede darse uno de estos dos casos: (i) que la llamada que visita w sea descendiente de la llamada que visita v en el bosque de llamadas recursivas, o (ii) que no lo sea, en cuyo caso es porque w había sido visitado antes de visitar v. En cualquiera de los dos casos se cumple que la llamada que visita w termina antes que la llamada que visita v. En el siguiente algoritmo aprovechamos eso para situar a v en la ordenación topológica después de que todos los vértices alcanzables desde v ya han sido situados, y situarlo por delante de ellos en la ordenación topológica es equivalente a situarlo por encima de ellos en una pila.

void GrafoDirigido::obtenerOrdenTopologicoDFS(int vertice,
					      vector<bool> & visitado,
					      stack<int> & ordenTopologico) const {

   visitado[vertice] = true;

   for (Arco * arco = vertices[vertice].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente) {
      int vecino = arco->vecino;
      if (! visitado[vecino])
	 obtenerOrdenTopologicoDFS(vecino, visitado, ordenTopologico);
   }

   ordenTopologico.push(vertice);

}

void GrafoDirigido::mostrarOrdenTopologico() const { // Suponemos grafo aciclico

   int cantidadDeVertices = vertices.size();

   vector<bool> visitado(cantidadDeVertices, false);
   stack<int> ordenTopologico;

   for (int vertice = 0; vertice < cantidadDeVertices; vertice++)
      if (! visitado[vertice])
	 obtenerOrdenTopologicoDFS(vertice, visitado, ordenTopologico);

   cout << "Ordenacion topologica:" << endl;
   while (! ordenTopologico.empty()) {
      int vertice = ordenTopologico.top();
      ordenTopologico.pop();
      cout << vertice << endl;
   }

}