Implementación de BFS en Java para Optimización de Rutas de Entrega en Grafos

Implementación de Algoritmos de Búsqueda en Amplitud (BFS) para la Gestión de Rutas

El siguiente código en Java demuestra la aplicación del algoritmo de Búsqueda en Amplitud (BFS) para encontrar la ruta más corta entre dos nodos en un grafo, simulando un escenario de entrega de periódicos donde se contabilizan los artículos entregados en el recorrido.

Clase Principal y Ejecución del Programa

La clase examen contiene el método principal (main) que inicializa el grafo, define los nodos de inicio y fin, y ejecuta el algoritmo BFS.

public class examen {
    public static void main(String[] args) {
        Graph g = new TreeMapGraph();
        crearGrafo(g);
        imprimirGrafo(g);

        // Configuración de nodos de inicio y destino
        String startNode = "6";
        String endNode = "3";
        
        Vertex s = g.getVertex(startNode);
        Vertex t = g.getVertex(endNode);

        // Validación rápida de nodos
        if (s == null || t == null) {
            System.out.println("\nUno o ambos nodos no existen en el grafo.");
            return;
        }

        // Ejecutar BFS y manejar resultado
        ElementoDecorado node = rutaBFS(g, s, t);
        
        if (node == null) {
            System.out.println("\nNo existe una ruta entre los nodos.");
            return;
        }

        // Reconstruir y mostrar ruta
        System.out.println("\nÚltimo vértice visitado: " + node.getID());
        
        if (node.getAntecesor() == null) {
            // Este caso solo debería ocurrir si el nodo inicial es el destino y no tiene antecesor.
            System.out.println("\nEsta no es la ruta (posiblemente inicio = destino).");
            return;
        }

        Stack<ElementoDecorado> stackV = new Stack<>();
        while (node != null) {
            stackV.push(node);
            node = node.getAntecesor();
        }

        System.out.println("\nRuta:");
        boolean first = true;
        while (!stackV.isEmpty()) {
            if (!first) System.out.print(" -> ");
            System.out.print(stackV.pop().getID());
            first = false;
        }
        System.out.println();
    }

Implementación del Algoritmo BFS (rutaBFS)

Este método implementa el algoritmo BFS para encontrar la ruta más corta y, simultáneamente, contabiliza los periódicos asociados a las viviendas activas encontradas en dicha ruta.

    // Método que implementa el algoritmo BFS para encontrar la ruta más corta.
    public static ElementoDecorado rutaBFS(Graph g, Vertex s, Vertex t) {
        Iterator<Vertex> itV;
        Iterator<Edge> itE;
        Queue<Vertex> q = new LinkedList<>(); // Cola para manejar los nodos en BFS.
        boolean destNoEnc = true; // Indica si el destino aún no se ha encontrado.
        Vertex u, v = null;
        Edge e;
        ElementoDecorado vLabel = null;
        int totalPeriodicos = 0; // Contador para los periódicos entregados.

        // 1. Inicializamos las etiquetas para cada nodo en el grafo (marcar como no visitado).
        itV = g.getVertices();
        while (itV.hasNext()) {
            u = itV.next();
            vLabel = (ElementoDecorado) u.getDecorator(); // Obtenemos el decorador del nodo.
            vLabel.setVisitado(false); // Marcamos el nodo como no visitado.
        }

        // 2. Contamos los periódicos del nodo inicial si está activo.
        ElementoDecorado decoradorInicial = (ElementoDecorado) s.getDecorator();
        // Obtenemos el decorador del nodo inicial 's'. Este decorador contiene información adicional
        // como si el nodo ha sido visitado y el objeto asociado al nodo (en este caso, ViviendaSuscrita).
        ViviendaSuscrita viviendaInicial = (ViviendaSuscrita) decoradorInicial.elemento();
        // Extraemos el objeto 'ViviendaSuscrita' desde el decorador. Este objeto contiene los datos
        // específicos del nodo, como si está activa y cuántos periódicos tiene asignados.
        if (viviendaInicial.isActiva()) {
            // Verificamos si la vivienda inicial está activa. Solo sumaremos periódicos si está activa.
            totalPeriodicos += viviendaInicial.getNumPeriodicos();
            // Si la vivienda está activa, añadimos el número de periódicos de esta vivienda al contador
            // total de periódicos entregados en la ruta.
        }

        // 3. Comienza el BFS desde el nodo inicial.
        decoradorInicial.setVisitado(true); // Marcamos el nodo inicial como visitado.
        q.offer(s); // Agregamos el nodo inicial a la cola.

        while (!q.isEmpty() && destNoEnc) {
            u = q.poll(); // Obtenemos el siguiente nodo de la cola.
            itE = g.incidentEdges(u); // Obtenemos las aristas incidentes al nodo.
            
            while (itE.hasNext() && destNoEnc) {
                e = itE.next();
                v = g.opposite(u, e); // Obtenemos el nodo opuesto en la arista.
                vLabel = (ElementoDecorado) v.getDecorator();
                
                if (!vLabel.getVisitado()) { // Si el nodo aún no ha sido visitado.
                    vLabel.setVisitado(true); // Marcamos el nodo como visitado.
                    vLabel.setAntecesor((ElementoDecorado) u.getDecorator()); // Asignamos su antecesor.
                    q.offer(v); // Agregamos el nodo a la cola para continuar explorando.
                    
                    // Verificamos si es el destino.
                    destNoEnc = !(v.getData().equals(t.getData())); 
                    
                    // Contamos periódicos si la vivienda está activa.
                    ViviendaSuscrita vivienda = (ViviendaSuscrita) vLabel.elemento();
                    if (vivienda.isActiva()) {
                        totalPeriodicos += vivienda.getNumPeriodicos(); // Suma periódicos si está activa.
                    }
                }
            }
        }

        if (destNoEnc) {
            System.out.println("No se encontró una ruta."); // Mensaje si no hay ruta.
            return null;
        }

        // Mostramos el total de periódicos entregados.
        System.out.println("Total de periódicos entregados en la ruta: " + totalPeriodicos);
        return (ElementoDecorado) t.getDecorator(); // Retornamos el decorador del nodo destino.
    }

Métodos Auxiliares: Creación e Impresión del Grafo

h4>Método crearGrafo

Este método inicializa la estructura del grafo, insertando vértices y aristas, y asociando datos de ViviendaSuscrita a cada nodo mediante el patrón Decorator.

    // Método para inicializar el grafo con los datos de viviendas.
    public static void crearGrafo(Graph gr) {
        // Creamos los vértices del grafo (ejemplo de 6 nodos).
        Vertex v1 = gr.insertVertex("1");
        Vertex v2 = gr.insertVertex("2");
        Vertex v3 = gr.insertVertex("3");
        Vertex v4 = gr.insertVertex("4");
        Vertex v5 = gr.insertVertex("5");
        Vertex v6 = gr.insertVertex("6");

        // Asociamos datos de ViviendaSuscrita a cada vértice.
        v1.setDecorator(new ElementoDecorado<>("1", new ViviendaSuscrita(true, 5))); // Nodo activo con 5 periódicos.
        v2.setDecorator(new ElementoDecorado<>("2", new ViviendaSuscrita(false, 0))); // Nodo inactivo.
        v3.setDecorator(new ElementoDecorado<>("3", new ViviendaSuscrita(true, 2))); // Nodo activo con 2 periódicos.
        v4.setDecorator(new ElementoDecorado<>("4", new ViviendaSuscrita(true, 1))); // Nodo activo con 1 periódico.
        v5.setDecorator(new ElementoDecorado<>("5", new ViviendaSuscrita(true, 3))); // Nodo activo con 3 periódicos.
        v6.setDecorator(new ElementoDecorado<>("6", new ViviendaSuscrita(true, 4))); // Nodo activo con 4 periódicos.

        // Creamos las conexiones (aristas) entre los nodos.
        // Se establece una ruta de ejemplo que incluye 6 y 3.
        gr.insertEdge(v1, v2, "1-2");
        gr.insertEdge(v6, v5, "6-5");
        gr.insertEdge(v5, v4, "5-4");
        gr.insertEdge(v4, v3, "4-3");
        gr.insertEdge(v1, v4, "1-4");
    }

h4>Método imprimirGrafo

Muestra las conexiones existentes en el grafo.

    // Método para imprimir las conexiones del grafo.
    public static void imprimirGrafo(Graph gr) {
        Vertex v[];
        Iterator<Edge> ite;
        System.out.println("Estructura del Grafo:");
        ite = gr.getEdges(); // Obtenemos las aristas del grafo.
        while (ite.hasNext()) {
            v = gr.endVertices(ite.next()); // Obtenemos los extremos de cada arista.
            System.out.print(v[0].getData().toString());
            System.out.print("-" + v[1].getData().toString() + "//"); // Imprimimos cada conexión.
        }
        System.out.println();
    }
}