Curso 2024/2025
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.
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; }
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; }
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; }
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; }