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.

Ejemplo de solución incorrecta 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;

}

Ejemplo de solución incorrecta 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;

}

Ejemplo de solución incorrecta 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;

}

Ejemplo de solución incorrecta 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;

}