Curso 2024/2025
Se muestran a continuación dos soluciones basadas en el algoritmo de Kahn.
Nos dicen que el grafo es acíclico, por lo que no hace falta comprobar eso.
El coste temporal y espacial de ambas soluciones es el del algoritmo de Kahn: O(|V| + |E|).
Una forma de resolver este ejercicio es partir del algoritmo de Kahn y añadir
dos contadores anyos
y simultaneas
como se muestra
a continuación.
int GrafoDirigido::minimaCantidadAnyos() const { vector<int> entradasRestantes(vertices.size()); queue<int> cajaDeVerticesConCeroEntradasRestantes; for (int v = 0; v < vertices.size(); v++) { entradasRestantes[v] = vertices[v].gradoDeEntrada; if (entradasRestantes[v] == 0) cajaDeVerticesConCeroEntradasRestantes.push(v); } int anyos = 0; int simultaneas = cajaDeVerticesConCeroEntradasRestantes.size(); while (! cajaDeVerticesConCeroEntradasRestantes.empty()) { int v = cajaDeVerticesConCeroEntradasRestantes.front(); cajaDeVerticesConCeroEntradasRestantes.pop(); cout << "Asignatura " << v << ":\tanyo " << anyos + 1 << endl; for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente) if (--entradasRestantes[arco->vecino] == 0) cajaDeVerticesConCeroEntradasRestantes.push(arco->vecino); if (--simultaneas == 0) { anyos++; simultaneas = cajaDeVerticesConCeroEntradasRestantes.size(); } } return anyos; }
Otra forma de resolver este ejercicio es partir del algoritmo de Kahn y
añadir el vector anyo
como se muestra a continuación.
int GrafoDirigido::minimaCantidadAnyos() const { vector<int> entradasRestantes(vertices.size()); vector<int> anyo(vertices.size()); queue<int> cajaDeVerticesConCeroEntradasRestantes; int v; for (v = 0; v < vertices.size(); v++) { entradasRestantes[v] = vertices[v].gradoDeEntrada; if (entradasRestantes[v] == 0) { cajaDeVerticesConCeroEntradasRestantes.push(v); anyo[v] = 1; } } while (! cajaDeVerticesConCeroEntradasRestantes.empty()) { v = cajaDeVerticesConCeroEntradasRestantes.front(); cajaDeVerticesConCeroEntradasRestantes.pop(); cout << "Asignatura " << v << ":\tanyo " << anyo[v] << endl; for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente) if (--entradasRestantes[arco->vecino] == 0) { cajaDeVerticesConCeroEntradasRestantes.push(arco->vecino); anyo[arco->vecino] = anyo[v] + 1; } } return anyo[v]; // Es el ultimo v del bucle anterior }