Algoritmos y Estructuras de Datos (VJ1215)

vector<int> GrafoDirigido::arbolDeCaminosOptimosSinPesos(int origen) const {

   vector<bool> visitado(vertices.size(), false);
   vector<int> padre(vertices.size(), -1);

   queue<int> cola;

   padre[origen] = -2;
   visitado[origen] = true;
   cola.push(origen);

   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente)
	 if (! visitado[arco->vecino]) {
	    padre[arco->vecino] = v;
	    visitado[arco->vecino] = true;
	    cola.push(arco->vecino);
	 }
   }

   return padre;

}
      

La solución anterior ilustra cómo trabajar con un booleano visitado asociado a cada vértice, que es como se suele presentar la búsqueda en anchura y es algo con lo que puedes contar para resolver otros ejercicios. No obstante, en este ejercicio nos lo podríamos ahorrar, puesto que un vértice está visitado si y solo si su padre no es -1:

vector<int> GrafoDirigido::arbolDeCaminosOptimosSinPesos(int origen) const {

   vector<int> padre(vertices.size(), -1);

   queue<int> cola;

   padre[origen] = -2;
   cola.push(origen);

   while (! cola.empty()) {
      int v = cola.front();
      cola.pop();
      for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente)
	 if (padre[arco->vecino] == -1) {
	    padre[arco->vecino] = v;
	    cola.push(arco->vecino);
	 }
   }

   return padre;

}