Calculadora de Árbol de Expansión Mínimo
Calcula el árbol de expansión mínimo (MST) de un grafo ponderado utilizando el algoritmo de Kruskal o Prim. Incluye visualización interactiva del grafo, seguimiento paso a paso del algoritmo y animación de selección de aristas.
Tu bloqueador de anuncios impide que mostremos anuncios
MiniWebtool es gratis gracias a los anuncios. Si esta herramienta te ayudó, apóyanos con Premium (sin anuncios + herramientas más rápidas) o añade MiniWebtool.com a la lista de permitidos y recarga la página.
- O pásate a Premium (sin anuncios)
- Permite anuncios para MiniWebtool.com y luego recarga
Calculadora de Árbol de Expansión Mínimo
Bienvenido a la Calculadora de Árbol de Expansión Mínimo, una herramienta interactiva para computar el MST de un grafo ponderado utilizando el algoritmo de Kruskal o el de Prim. Ya sea que estés estudiando teoría de grafos, diseñando infraestructura de red u optimizando la asignación de recursos, esta calculadora proporciona una exploración visual y paso a paso de dos algoritmos fundamentales en la optimización combinatoria.
¿Qué es un Árbol de Expansión Mínimo (MST)?
Un Árbol de Expansión Mínimo de un grafo conectado, no dirigido y ponderado es un subconjunto de aristas que:
- Conecta todos los vértices juntos (expansión)
- No contiene ciclos (árbol)
- Tiene el peso total de aristas mínimo posible
Para un grafo con V vértices, un MST siempre tiene exactamente V - 1 aristas. Si el grafo está desconectado, el resultado es un Bosque de Expansión Mínimo: una colección de MSTs para cada componente conectado.
Algoritmo de Kruskal
El algoritmo de Kruskal es un algoritmo voraz basado en aristas que construye el MST procesando las aristas en orden de peso creciente. Utiliza una estructura de datos Union-Find (Unión-Búsqueda) para detectar ciclos de manera eficiente.
Pseudocódigo de Kruskal
MST ← conjunto vacío
Ordenar todas las aristas por peso (ascendente)
Inicializar Union-Find para todos los vértices
para cada arista (u, v, w) en las aristas ordenadas:
si Find(u) ≠ Find(v): // diferentes componentes
MST ← MST ∪ {(u, v, w)}
Union(u, v) // fusionar componentes
retornar MST
Algoritmo de Prim
El algoritmo de Prim es un algoritmo voraz basado en vértices que hace crecer el MST desde un vértice inicial. En cada paso, añade la arista más barata que conecta un vértice del árbol con un vértice fuera del árbol.
Pseudocódigo de Prim
MST ← conjunto vacío
enMST ← {inicio}
PQ ← cola de prioridad con aristas desde inicio
mientras PQ no esté vacía y |enMST| < |V|:
(w, u, v) ← extraer mín de PQ
si v ∉ enMST:
MST ← MST ∪ {(u, v, w)}
enMST ← enMST ∪ {v}
Añadir todas las aristas desde v a PQ
retornar MST
Kruskal vs Prim: ¿Cuándo usar cuál?
| Característica | Kruskal | Prim |
|---|---|---|
| Enfoque | Basado en aristas (ordenación global) | Basado en vértices (crecimiento local) |
| Estructura de Datos | Union-Find | Cola de Prioridad |
| Complejidad Temporal | \( O(E \log E) \) | \( O((V + E) \log V) \) |
| Ideal para | Grafos dispersos | Grafos densos |
| Grafos Desconectados | Produce un bosque de expansión | Solo expande el componente del nodo inicial |
| Paralelizable | Más fácil de paralelizar | Secuencial por naturaleza |
Cómo usar esta calculadora
- Define las aristas de tu grafo: Ingresa las aristas en el formato
nodo1, nodo2, peso, una por línea. El MST opera en grafos no dirigidos, por lo que cada arista funciona en ambas direcciones. - Elige un algoritmo: Selecciona Kruskal para grafos dispersos o Prim para grafos densos. Ambos producen un MST óptimo.
- Establece el nodo de inicio (solo Prim): Opcionalmente especifica dónde comienza el algoritmo de Prim. Esto afecta el orden de selección de las aristas pero no el peso total del MST.
- Computar MST: Haz clic en "Buscar MST" para ejecutar el algoritmo. Explora la visualización interactiva, la tabla de aristas y la traza paso a paso.
- Recorre los pasos: Usa los botones Siguiente/Anterior para ver el algoritmo ejecutarse paso a paso, con resaltado en el canvas en tiempo real.
Entendiendo los resultados
Tabla de Aristas del MST
Muestra cada arista seleccionada para el MST, en el orden en que fueron añadidas, junto con los pesos individuales y el peso total del MST.
Visualización del Grafo
El canvas interactivo muestra tu grafo con elementos codificados por colores:
- Nodos y aristas verdes = Parte del MST
- Resaltados naranjas = Actualmente bajo examen
- Elementos grises = Aún no forman parte del MST
Traza paso a paso
Muestra cada decisión del algoritmo: qué arista se examina, si fue aceptada o rechazada (y por qué), y el estado actual de la construcción del MST.
Aplicaciones del MST en el mundo real
Diseño de Redes
La aplicación más clásica. Al conectar nodos (ciudades, servidores, dispositivos eléctricos) con una longitud total mínima de cable, fibra o tubería, el MST proporciona la solución óptima. Las empresas de telecomunicaciones utilizan algoritmos basados en MST para minimizar los costos de infraestructura.
Análisis de Conglomerados
En aprendizaje automático y ciencia de datos, la agrupación basada en MST (como el clustering de enlace simple) agrupa puntos de datos eliminando las aristas más largas del MST. Esto produce grupos naturales sin necesidad de especificar previamente el número de grupos.
Segmentación de Imágenes
Los algoritmos de visión artificial utilizan MST para segmentar imágenes en regiones significativas. Los píxeles son nodos, los pesos de las aristas representan la diferencia en color/intensidad, y cortar aristas del MST separa objetos distintos.
Algoritmos de Aproximación
El MST proporciona una aproximación de factor 2 para el Problema del Viajante (TSP) métrico. El peso del MST es un límite inferior del recorrido óptimo del TSP, y duplicar las aristas del MST da un recorrido dentro del doble de lo óptimo.
Diseño de Circuitos
El diseño de chips VLSI utiliza MST (a través de variantes del árbol de Steiner) para minimizar la longitud total de los cables que conectan los componentes en una placa de circuito, reduciendo el retraso de la señal y el costo de fabricación.
Propiedades clave del MST
- Propiedad del Corte: Para cualquier corte del grafo, la arista de peso mínimo que cruza el corte está en el MST.
- Propiedad del Ciclo: Para cualquier ciclo en el grafo, la arista de peso máximo en el ciclo NO está en el MST (asumiendo pesos únicos).
- Unicidad: Si todos los pesos de las aristas son distintos, el MST es único. Con pesos duplicados, puede haber múltiples MSTs válidos con el mismo peso total.
- Subgrafo: El MST es un subgrafo con V-1 aristas y sin ciclos.
Preguntas Frecuentes
¿Qué es un Árbol de Expansión Mínimo (MST)?
Un Árbol de Expansión Mínimo es un subconjunto de aristas de un grafo conectado, no dirigido y ponderado que conecta todos los vértices con el peso total de aristas mínimo posible, sin formar ciclos. Un MST tiene exactamente V-1 aristas para un grafo con V vértices.
¿Cuál es la diferencia entre el algoritmo de Kruskal y el de Prim?
El algoritmo de Kruskal se basa en las aristas: ordena todas las aristas por peso y añade vorazmente aquellas que no crean ciclos, utilizando una estructura de datos Union-Find. El algoritmo de Prim se basa en los vértices: hace crecer el MST desde un nodo inicial añadiendo siempre la arista más barata que conecte el árbol con un nuevo vértice, utilizando una cola de prioridad. Ambos producen MSTs óptimos pero pueden diferir en el orden de selección de las aristas.
¿Cuándo debo usar el algoritmo de Kruskal frente al de Prim?
Kruskal es generalmente mejor para grafos dispersos (pocas aristas en relación a los nodos) con una complejidad temporal O(E log E). Prim es mejor para grafos densos con una complejidad temporal O(E log V) usando un montículo binario. Para grafos muy densos, Prim con un montículo de Fibonacci logra O(E + V log V).
¿Puede un grafo tener múltiples MSTs válidos?
Sí, un grafo puede tener múltiples MSTs válidos si hay aristas con pesos iguales. Los diferentes MSTs tendrán el mismo peso total pero pueden incluir aristas diferentes. Kruskal y Prim pueden producir diferentes MSTs para el mismo grafo, pero ambos tendrán el mismo peso total mínimo.
¿Cuáles son las aplicaciones del MST en el mundo real?
Los MSTs se utilizan en el diseño de redes (minimizando la longitud de cables/fibra), diseño de placas de circuitos, análisis de conglomerados, segmentación de imágenes, construcción de taxonomías, aproximación de problemas NP-duros como el Problema del Viajante (TSP) y la construcción de redes de carreteras/tuberías/eléctricas al costo mínimo.
¿Funciona el MST en grafos desconectados?
Un verdadero MST requiere un grafo conectado. Si el grafo está desconectado, los algoritmos producirán un Bosque de Expansión Mínimo: una colección de MSTs, uno para cada componente conectado. Esta calculadora indicará cuándo el grafo no está totalmente conectado.
Recursos Adicionales
Cite este contenido, página o herramienta como:
"Calculadora de Árbol de Expansión Mínimo" en https://MiniWebtool.com/es// de MiniWebtool, https://MiniWebtool.com/
por el equipo de miniwebtool. Actualizado: 19 de febrero de 2026
También puede probar nuestro Solucionador de Matemáticas AI GPT para resolver sus problemas matemáticos mediante preguntas y respuestas en lenguaje natural.