Algoritmos y Estructuras de Datos (VJ1215)

La existencia de un ciclo en el grafo se puede detectar porque, durante la búsqueda en profundidad, un vértice v tiene entre sus arcos de salida un arco (v, w) y w no solamente ya ha sido visitado sino que además es un ascendiente de v en el bosque de llamadas recursivas: eso implica que la búsqueda ya ha recorrido un camino desde w hasta v, y el arco (v, w) cierra un ciclo.

Para reconocer eficientemente que w es un ascendiente de v en el árbol de llamadas recursivas, cuando se está ejecutando la llamada que recibe v como argumento podemos comprobar que la llamada que recibe w ha empezado pero no ha terminado.

bool GrafoDirigido::buscarCicloDFS(int vertice,
				   vector<bool> & visitado,
				   vector<bool> & terminado) const {

   visitado[vertice] = true;

   for (Arco * arco = vertices[vertice].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente) {
      int vecino = arco->vecino;
      if (visitado[vecino] && ! terminado[vecino])
	 return true;
      if (! visitado[vecino])
	 if (buscarCicloDFS(vecino, visitado, terminado))
	    return true;
   }

   terminado[vertice] = true;

   return false;

}

bool GrafoDirigido::esAciclico() const {

   int cantidadDeVertices = vertices.size();
   
   vector<bool> visitado(cantidadDeVertices, false);
   vector<bool> terminado(cantidadDeVertices, false);

   for (int vertice = 0; vertice < cantidadDeVertices; vertice++)
      if (! visitado[vertice])
	 if (buscarCicloDFS(vertice, visitado, terminado))
	    return false;
   return true;

}
      

Una solución equivalente consiste en hacer con un vector de enteros estado lo que se hace en la solución anterior con dos vectores de booleanos. En la siguiente solución, el valor de estado[w] permite saber si la llamada que recibe w como argumento ya ha terminado (estado 2), ha empezado pero no ha terminado (estado 1) o no ha empezado (estado 0). El estado 0 hace el mismo papel que un booleando que indica que no ha sido visitado.

bool GrafoDirigido::buscarCicloDFS(int vertice,
                                   vector<int> & estado) const {

   estado[vertice] = 1;

   for (Arco * arco = vertices[vertice].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente) {
      int vecino = arco->vecino;
      if (estado[vecino] == 1)
	 return true;
      if (estado[vecino] == 0)
	 if (buscarCicloDFS(vecino, estado))
	    return true;
   }

   estado[vertice] = 2;

   return false;

}

bool GrafoDirigido::esAciclico() const {

   int cantidadDeVertices = vertices.size();
   
   vector<int> estado(cantidadDeVertices, 0);

   for (int vertice = 0; vertice < cantidadDeVertices; vertice++)
      if (estado[vertice] == 0)
	 if (buscarCicloDFS(vertice, estado))
	    return false;
   return true;

}