Taller: Árbol de Recubrimiento Mínimo ‐ Algoritmo de Kruskal - emilioone05/Analisis_Algoritmos_utpl GitHub Wiki

Fecha de entrega: lunes 28 de julio de 2025
Estudiante: Emilio Jose Peña Armijos

1. Introducción

Este proyecto implementa el algoritmo de Kruskal en Java para encontrar el Árbol de Recubrimiento Mínimo (MST) en un grafo no dirigido. El contexto está basado en el universo de DC Comics, específicamente entre los personajes Green Arrow y Red Hood, quienes deben conectar los distintos distritos de Star City (ciudad natal de Green Arrow) con caminos seguros y de menor costo posible.

2. Implementación en Java

Código Completo

import java.util.*;

class Arista {
    int origen, destino, peso;

    Arista(int origen, int destino, int peso) {
        this.origen = origen;
        this.destino = destino;
        this.peso = peso;
    }
}

class Grafo {
    int vertices;
    List<Arista> aristas;

    Grafo(int vertices) {
        this.vertices = vertices;
        this.aristas = new ArrayList<>();
    }

    void agregarArista(int origen, int destino, int peso) {
        aristas.add(new Arista(origen, destino, peso));
    }

    int encontrar(int[] padre, int i) {
        if (padre[i] != i)
            padre[i] = encontrar(padre, padre[i]);
        return padre[i];
    }

    void unir(int[] padre, int[] rango, int x, int y) {
        int raizX = encontrar(padre, x);
        int raizY = encontrar(padre, y);

        if (rango[raizX] < rango[raizY]) {
            padre[raizX] = raizY;
        } else if (rango[raizX] > rango[raizY]) {
            padre[raizY] = raizX;
        } else {
            padre[raizY] = raizX;
            rango[raizX]++;
        }
    }

    void kruskal() {
        List<Arista> resultado = new ArrayList<>();
        Collections.sort(aristas, Comparator.comparingInt(a -> a.peso));

        int[] padre = new int[vertices];
        int[] rango = new int[vertices];

        for (int i = 0; i < vertices; i++) {
            padre[i] = i;
            rango[i] = 0;
        }

        for (Arista arista : aristas) {
            int x = encontrar(padre, arista.origen);
            int y = encontrar(padre, arista.destino);

            if (x != y) {
                resultado.add(arista);
                unir(padre, rango, x, y);
            }
        }

        System.out.println("Conexiones mínimas para proteger Star City:");
        for (Arista arista : resultado) {
            System.out.printf("Distrito %d ↔ Distrito %d con costo %d%n", arista.origen, arista.destino, arista.peso);
        }
    }
}

public class StarCityProtegida {
    public static void main(String[] args) {
        Grafo grafo = new Grafo(6);
        
        grafo.agregarArista(0, 1, 4);
        grafo.agregarArista(0, 2, 3);
        grafo.agregarArista(1, 2, 1);
        grafo.agregarArista(1, 3, 2);
        grafo.agregarArista(2, 3, 4);
        grafo.agregarArista(3, 4, 2);
        grafo.agregarArista(4, 5, 6);

        grafo.kruskal();
    }
}

3. Resultados Obtenidos

Salida esperada en consola

Conexiones mínimas para proteger Star City:
Distrito 1 ↔ Distrito 2 con costo 1
Distrito 1 ↔ Distrito 3 con costo 2
Distrito 3 ↔ Distrito 4 con costo 2
Distrito 0 ↔ Distrito 2 con costo 3
Distrito 4 ↔ Distrito 5 con costo 6

Este conjunto de conexiones representa el Árbol de Recubrimiento Mínimo (MST), garantizando que todos los distritos estén conectados con el menor costo posible.

4. Análisis

  • El algoritmo de Kruskal ordena las aristas por peso y va agregando las más baratas mientras evita ciclos.
  • En el contexto de Star City, esto significa usar los recursos más eficientemente para proteger los distritos.
  • Green Arrow y Red Hood colaboran en este caso para enfrentar una amenaza que requiere máxima cobertura territorial con el mínimo de recursos.

5. Conclusiones

  • El algoritmo de Kruskal es eficiente para encontrar un MST en grafos no dirigidos.
  • Es ideal para problemas de conexión donde el costo debe ser minimizado.
  • El uso del contexto de Star City y los héroes ayuda a comprender de forma práctica y entretenida cómo se pueden aplicar estos algoritmos en el mundo real.
⚠️ **GitHub.com Fallback** ⚠️