Algoritmos y Estructuras de Datos (VJ1215)

Para resolver este problema, basta con realizar una búsqueda en anchura que parta del vértice origen dado, y contar cuántos vértices son visitados en esa búsqueda para comprobar si son todos los del grafo.

bool GrafoDirigido::todosAlcanzablesDesdeVertice(int origen) const {

   vector<bool> visitado(vertices.size(), false);
   queue<int> cola;
   int contadorVisitados;

   visitado[origen] = true;
   contadorVisitados = 1;
   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]) {
	    visitado[arco->vecino] = true;
	    contadorVisitados++;
	    cola.push(arco->vecino);
	 }
   }

   // cout << "Cantidad de vertices alcanzables desde " << origen << ": " << contadorVisitados << endl;

   return contadorVisitados == vertices.size();

}
      

Otra solución válida consiste en añadir a la solución del ejercicio 2.a un bucle que comprueba si queda algún -1 en el vector padre (o si queda algún false en el vector visitado, es equivalente) tras vaciarse la cola:

bool GrafoDirigido::todosAlcanzablesDesdeVertice(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);
	 }
   }

   for (int p : padre)
      if (p == -1)
         return false;
   return true;

}
      

Si el grafo fuese no dirigido, podríamos aplicar el mismo algoritmo sin más que considerar que, en cualquier vértice, todos los arcos que conectan ese vértice con otros son arcos de salida (también son arcos de entrada).