Curso 2024/2025
El algoritmo de Kahn resuelve también el problema de averiguar si hay ciclos, como hemos visto en el ejercicio 4. El coste temporal y espacial de este algoritmo es O(|V| + |E|) con una representación del grafo mediante listas de adyacencia.
Si el único resultado que nos interesa es ese, quedaría así:
bool GrafoDirigido::esAciclico() const { vector<int> entradasRestantes(vertices.size()); queue<int> caja; int contadorDeVertices = 0; for (int v = 0; v < vertices.size(); v++) { entradasRestantes[v] = vertices[v].gradoDeEntrada; if (entradasRestantes[v] == 0) caja.push(v); } while (! caja.empty()) { int v = caja.front(); caja.pop(); contadorDeVertices++; for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente) if (--entradasRestantes[arco->vecino] == 0) caja.push(arco->vecino); } return contadorDeVertices == vertices.size(); }