Algoritmo de Prim para la obtención de árboles de expansión mínima en Grafos Ponderados

Abstract

Los algoritmos voraces constituyen una de las estrategias algorítmicas más utilizadas para resolver problemas de optimización en informática. Entre ellos, el algoritmo de Prim destaca por su capacidad para construir árboles de expansión mínima en grafos ponderados conectados. El objetivo de esta investigación es analizar el funcionamiento, aplicación y eficiencia del algoritmo de Prim dentro del contexto de las estrategias algorítmicas. La metodología empleada consistió en una revisión bibliográfica de literatura especializada y en el análisis de ejemplos prácticos aplicados a grafos ponderados. Los resultados preliminares muestran que el algoritmo permite obtener soluciones óptimas mediante la selección iterativa de aristas de menor costo, garantizando la conexión de todos los vértices sin generar ciclos. Asimismo, se evidencia su importancia en problemas relacionados con diseño de redes, telecomunicaciones y sistemas de transporte. Se concluye que el algoritmo de Prim representa una alternativa eficiente para la construcción de árboles de expansión mínima, especialmente en grafos densos donde la minimización de costos resulta fundamental.