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

  1. BFS (Menor cantidad de saltos):
    • Mantener un conjunto Set<Estacion> visitados y una cola Queue<Estacion> cola.
    • Registrar en un Map<Estacion, Estacion> predecesores para reconstruir el recorrido.
  2. Dijkstra (Menor tiempo acumulado):
    • Mantener un Map<Estacion, Double> distancias inicializado en infinito.
    • Encolar en PriorityQueue instancias 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$.