Curso 2024/2025
void GrafoDirigido::mostrarOrdenTopologico() const { cout << "Ordenacion topologica:" << endl; vector<int> entradasRestantes(vertices.size()); vector<int> ordenTopologico(vertices.size()); queue<int> cajaDeVerticesConCeroEntradasRestantes; // En este algoritmo tambien se podria usar stack int contadorDeVertices = 0; for (int v = 0; v < vertices.size(); v++) { entradasRestantes[v] = vertices[v].gradoDeEntrada; if (entradasRestantes[v] == 0) cajaDeVerticesConCeroEntradasRestantes.push(v); } while (! cajaDeVerticesConCeroEntradasRestantes.empty()) { int v = cajaDeVerticesConCeroEntradasRestantes.front(); cajaDeVerticesConCeroEntradasRestantes.pop(); ordenTopologico[contadorDeVertices++] = v; for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente) if (--entradasRestantes[arco->vecino] == 0) cajaDeVerticesConCeroEntradasRestantes.push(arco->vecino); } if (contadorDeVertices != vertices.size()) throw string ("ERROR: el grafo no es aciclico"); for (int v : ordenTopologico) cout << v << endl; }