Curso 2024/2025
vector<int> GrafoDirigido::arbolDeCaminosOptimosSinPesos(int origen) const { vector<bool> visitado(vertices.size(), false); vector<int> padre(vertices.size(), -1); queue<int> cola; padre[origen] = -2; visitado[origen] = true; cola.push(origen); while (! cola.empty()) { int v = cola.front(); cola.pop(); for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente) if (! visitado[arco->vecino]) { padre[arco->vecino] = v; visitado[arco->vecino] = true; cola.push(arco->vecino); } } return padre; }
La solución anterior ilustra cómo trabajar con un
booleano visitado
asociado a cada vértice, que es como se suele
presentar la búsqueda en anchura y es algo con lo que puedes contar para
resolver otros ejercicios. No obstante, en este ejercicio nos lo podríamos
ahorrar, puesto que un vértice está visitado si y solo si su padre no es -1:
vector<int> GrafoDirigido::arbolDeCaminosOptimosSinPesos(int origen) const { vector<int> padre(vertices.size(), -1); queue<int> cola; padre[origen] = -2; cola.push(origen); while (! cola.empty()) { int v = cola.front(); cola.pop(); for (Arco * arco = vertices[v].primerArcoDeSalida; arco != nullptr; arco = arco->siguiente) if (padre[arco->vecino] == -1) { padre[arco->vecino] = v; cola.push(arco->vecino); } } return padre; }