Curso 2023/2024
La búsqueda en anchura se puede adaptar fácilmente para averiguar si un vértice t es alcanzable desde un vértice s, basta con añadir esto a una búsqueda en anchura que parta desde s:
Antes de insertar un vértice en la cola, si es t terminamos devolviendo cierto.
Tras vaciarse la cola, terminamos devolviendo falso.
El coste temporal y espacial de este algoritmo es O(|V| + |E|) con una representación del grafo mediante listas de adyacencia.
bool GrafoDirigido::esAlcanzable(int origen, int destino) const { if (origen == destino) return true; queue<int> cola; vector<bool> visitado(vertices.size(), false); 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]) { if (arco->vecino == destino) return true; visitado[arco->vecino] = true; cola.push(arco->vecino); } } return false; }