Algoritmos y Estructuras de Datos - VJ1215

Ejemplos de soluciones incorrectas en el ejercicio 25.a del tema 6

Cada una de las siguientes soluciones contiene un error, piensa cuál es. Después, compara el código con la solución del ejercicios 25.a para ver lo que falta.

Error 1

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])
	 buscarCicloDFS(vecino, visitado, terminado)
   }

   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;

}

Error 2

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])
	 return buscarCicloDFS(vecino, visitado, terminado)
   }

   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;

}

Error 3

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

   visitado[vertice] = true;

   bool hayCiclo = false;

   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])
	 hayCiclo = buscarCicloDFS(vecino, visitado, terminado);
   }

   terminado[vertice] = true;

   return hayCiclo;

}

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;

}

Error 4

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 (! 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;

}