Arbol de cobertura Mínimo(MST)

Arbol de cobertura Mínimo(MST)

Dado una red G(V,A) un árbol de cobertura mínimo es el árbol que conecta todos los vértices de la red con n-1 arcos (n siendo el numero de vértices y m el numero de arcos) pero con el menor costo total.

Los dos algoritmos más importantes para determinar cobertura mínima son:

Algoritmo de Kruskal (1956). El cual primero ordena todos los arcos en orden no decrecientes, después los examina de menor a mayor costo de la red y si no forman ciclos con los ya seleccionados, se incorporan al árbol de cobertura mínima. La construcción se detiene cuando se han seleccionados, los n-1 arcos o se han examinado los m arcos de la red.
Algoritmo de Prim's(1957). Construye un árbol de cobertura partiendo con un vértice arbitrario s el cual se une con los vecinos más cercanos examinando los arcos incidentes a s que posee el menor costo hasta revisar todos los arcos de la red.

Para grafos pequeños (hasta 100 nodos) Prim's funciona mejor, pero para grafos mayores y densos Kruskal presenta un mejor desempeño.