Contexto
Cuando las relaciones entre entidades superan las restricciones jerárquicas de un árbol (donde no hay ciclos y cada nodo tiene un solo padre), el Grafo es la estructura adecuada. Un mapa de rutas viales, una red eléctrica o las conexiones de vuelos son grafos: conjuntos de vértices unidos por aristas con sentido (dirigidos) y costos asociados (ponderados).
La elección de la estructura interna impacta directamente en el rendimiento:
- Lista de adyacencia: óptima para grafos dispersos (sparse graphs), ocupando $O(V + E)$ en memoria y permitiendo iterar eficientemente sobre los vecinos directos de cada vértice.
- Búsqueda en Anchura (BFS): explora por capas concéntricas utilizando una Cola (FIFO), garantizando encontrar el camino más corto en cantidad de aristas (menor número de transbordos).
- Algoritmo de Dijkstra: explora mediante una Cola de Prioridad, garantizando encontrar el camino de mínimo costo acumulado (menor tiempo o distancia) en grafos con pesos positivos.
Consigna
Vas a implementar un sistema de enrutamiento de transporte público en Java.
1. Modelo de Dominio
public class Estacion {
private final String id;
private final String nombre;
// constructor, getters, equals y hashCode basados en id
}
public class Arista {
private final Estacion destino;
private final double peso; // minutos de viaje
// constructor y getters
}
2. Estructura del Grafo con Lista de Adyacencia
public class GrafoTransporte {
private final Map<Estacion, List<Arista>> adyacencia = new HashMap<>();
public void agregarEstacion(Estacion estacion) {
adyacencia.putIfAbsent(estacion, new ArrayList<>());
}
public void conectarBidireccional(Estacion a, Estacion b, double minutos) {
if (minutos <= 0) throw new IllegalArgumentException("El tiempo debe ser mayor a cero");
if (!adyacencia.containsKey(a) || !adyacencia.containsKey(b)) {
throw new IllegalArgumentException("Ambas estaciones deben pertenecer al grafo");
}
adyacencia.get(a).add(new Arista(b, minutos));
adyacencia.get(b).add(new Arista(a, minutos));
}
}
3. Algoritmos de Búsqueda y Enrutamiento
- BFS (Menor cantidad de saltos):
- Mantener un conjunto
Set<Estacion> visitadosy una colaQueue<Estacion> cola. - Registrar en un
Map<Estacion, Estacion> predecesorespara reconstruir el recorrido.
- Mantener un conjunto
- Dijkstra (Menor tiempo acumulado):
- Mantener un
Map<Estacion, Double> distanciasinicializado en infinito. - Encolar en
PriorityQueueinstancias de(estacion, distanciaActual). - Cuando se relaja una arista $(u, v)$ con peso $w$: si $distancia[u] + w < distancia[v]$, actualizar $distancia[v]$ y registrar $u$ como predecesor de $v$.
- Mantener un