Curso 2024/2025
En este ejercicio podemos aplicar de nuevo un razonamiento que hemos visto en el ejercicio 3.c.
La solución eficiente consiste en hacer una búsqueda en anchura o en profundidad desde q en el grafo invertido, que es lo mismo que hacer una búsqueda desde q recorriendo los arcos de entrada, y terminar cuando todos los vértices con ratón son visitados o cuando no hay más vértices alcanzables desde q en el grafo invertido. El coste temporal es O(|V| + |E|) con una representación del grafo que incluya listas de arcos de entrada.
bool GrafoConEnlaces::quesoAlcanzablePorTodosLosRatones(int queso, const vector<bool> & raton) const { int cantidadDeVertices = vertices.size(); vector<bool> visitado(cantidadDeVertices, false); queue<int> cola; int cantidadDeRatonesPorVisitar = 0; for (int v = 0; v < cantidadDeVertices; v++) if (raton[v]) cantidadDeRatonesPorVisitar++; if (cantidadDeRatonesPorVisitar == 0) throw string("Faltan los ratones"); if (raton[queso] && --cantidadDeRatonesPorVisitar == 0) return true; visitado[queso] = true; cola.push(queso); while (! cola.empty()) { int v = cola.front(); cola.pop(); for (Arco * arco = vertices[v].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente) if (! visitado[arco->vecino]) { if (raton[arco->vecino] && --cantidadDeRatonesPorVisitar == 0) return true; visitado[arco->vecino] = true; cola.push(arco->vecino); } } return false; }
bool GrafoConEnlaces::buscarRatonesDFS(int v, const vector<bool> & raton, int & cantidadDeRatonesPorVisitar, vector<bool> & visitado) const { if (raton[v] && --cantidadDeRatonesPorVisitar == 0) return true; visitado[v] = true; for (Arco * arco = vertices[v].primerArcoDeEntrada; arco != nullptr; arco = arco->siguiente) if (! visitado[arco->vecino]) if (buscarRatonesDFS(arco->vecino, raton, cantidadDeRatonesPorVisitar, visitado)) return true; return false; } bool GrafoConEnlaces::quesoAlcanzablePorTodosLosRatones(int queso, const vector<bool> & raton) const { int cantidadDeVertices = vertices.size(); vector<bool> visitado(cantidadDeVertices, false); int cantidadDeRatonesPorVisitar = 0; for (int v = 0; v < cantidadDeVertices; v++) if (raton[v]) cantidadDeRatonesPorVisitar++; if (cantidadDeRatonesPorVisitar == 0) throw string("Faltan los ratones"); return buscarRatonesDFS(queso, raton, cantidadDeRatonesPorVisitar, visitado); }