Un grafo es lo que tienes en la imagen que has puesto en el mensaje: Una serie de nodos unidos entre ellos. Vale, puede ser una descripción un poco vaga pero para lo que necesitas sirve.
Los pesos los puedes interpretar como el coste de llegar de un nodo A a otro B mediante la unión que los une. El peso no tiene unidades y es, por tanto, algo abstracto. Puede significar lo que tu quieras: distancia (mayor peso mayor distancia. p.ej: 1peso=1metro), tiempo para cruzar la unión (mayor peso mayor tiempo. p.ej: 1peso=1minuto), ...
Todo lo anterior, repito, cubre únicamente una parte de la temática de los grafos, pero con eso ya se podría empezar a trabajar en el ejercicio.
En el caso del ejercicio de tu hija, para que tenga algo de sentido, puedes entender que los pesos significan tiempo y te están pidiendo que encuentres una ruta en la que se inviertan 84 minutos.
Para orientarse en un grafo hay que usar algoritmos de encaminamiento. Estos algoritmos permiten calcular rutas más o menos óptimas entre dos puntos cualesquiera del grafo.
En cualquier caso estos algoritmos suelen hacer uso intensivo de listas y árboles, ya que suelen tantear varias rutas antes de elegir la que creen más óptima.
He sacado un ratillo y me ha picado el gusanillo. Un código que navega por un grafo y busca una ruta con el peso pedido:
Código C++:
Ver original#include <algorithm>
#include <iostream>
#include <vector>
struct Posicion
{
size_t fila;
size_t columna;
Posicion(size_t fila, size_t columna)
: fila(fila),
columna(columna)
{ }
bool operator==(const Posicion& otra) const
{
return (fila == otra.fila) && (columna == otra.columna);
}
};
using Ruta = std::vector<Posicion>;
class Grafo
{
std::vector<int> _valores;
size_t _numFilas;
size_t _numColumnas;
public:
Grafo(size_t filas, size_t columnas, int* valores)
: _numFilas(filas),
_numColumnas(columnas)
{
// Copiamos los datos en el grafo
_valores.reserve(filas*columnas);
for( size_t i=filas*columnas; i>0; --i)
{
_valores.push_back(*valores);
++valores;
}
}
size_t NumFilas() const
{ return _numFilas; }
size_t NumColumnas() const
{ return _numColumnas; }
int Valor(const Posicion& posicion) const
{ return _valores[posicion.fila * _numColumnas + posicion.columna]; }
};
// Verifica que la nueva posición es válida.
// Se entiende que es válida si está dentro de los límites del grafo
// y si la posición no ha sido usada.
bool PosicionValida(
const Grafo& grafo,
const Ruta& ruta,
const Posicion& nuevaPosicion)
{
auto toReturn = (nuevaPosicion.fila < grafo.NumFilas());
if( toReturn )
toReturn = (nuevaPosicion.columna < grafo.NumColumnas());
if( toReturn )
{
auto it = std::find(ruta.begin(),ruta.end(),nuevaPosicion);
toReturn = (it == ruta.end());
}
return toReturn;
}
bool BuscarRuta(
const Grafo& grafo,
const Posicion& nuevaPosicion,
const Posicion& destino,
Ruta& ruta,
int pesoActual,
int pesoEsperado)
{
auto toReturn = false;
if( PosicionValida(grafo,ruta,nuevaPosicion) )
{
ruta.push_back(nuevaPosicion);
auto nuevoPeso = grafo.Valor(nuevaPosicion);
pesoActual += nuevoPeso;
if( nuevaPosicion == destino )
toReturn = pesoActual == pesoEsperado;
else if( pesoActual >= pesoEsperado )
toReturn = false;
else
{
// Intentamos avanzar hacia arriba
auto nueva = Posicion(nuevaPosicion.fila-1,nuevaPosicion.columna);
toReturn = BuscarRuta(grafo,nueva,destino,ruta,pesoActual,pesoEsperado);
if( !toReturn )
{
// Intentamos avanzar hacia la derecha
auto nueva = Posicion(nuevaPosicion.fila,nuevaPosicion.columna+1);
toReturn = BuscarRuta(grafo,nueva,destino,ruta,pesoActual,pesoEsperado);
}
if( !toReturn )
{
// Intentamos avanzar hacia abajo
auto nueva = Posicion(nuevaPosicion.fila+1,nuevaPosicion.columna);
toReturn = BuscarRuta(grafo,nueva,destino,ruta,pesoActual,pesoEsperado);
}
if( !toReturn )
{
// Intentamos avanzar hacia la izquierda
auto nueva = Posicion(nuevaPosicion.fila,nuevaPosicion.columna-1);
toReturn = BuscarRuta(grafo,nueva,destino,ruta,pesoActual,pesoEsperado);
}
}
if( !toReturn )
{
// Si no se ha encontrado una ruta válida se borra la posición
// que hemos registrado al inicio de la función
ruta.pop_back();
pesoActual -= nuevoPeso;
}
}
return toReturn;
}
int main()
{
int valores[] = {6, 1, 9, 2, 4, 5,
3, 7, 1, 5, 5, 9,
5, 3, 4, 8, 7, 1,
1, 3, 1, 4, 5, 3,
3, 4, 8, 9, 2, 7};
auto grafo = Grafo(5, 6, valores);
auto posActual = Posicion(4,5);
auto posFinal = Posicion(4,0);
Ruta ruta;
BuscarRuta(grafo,posActual,posFinal,ruta,0,48);
if( ruta.empty() )
std::cout << "No se ha encontrado ninguna ruta" << std::endl;
else
{
std::cout << "Ruta encontrada:" << std::endl;
for( auto posicion : ruta )
std::cout << "(" << posicion.fila << "," << posicion.columna << ")" << std::endl;
}
return EXIT_SUCCESS;
}
PD.: el algoritmo encuentra una ruta alternativa a la que has encontrado tu :)