Algoritmo del árbol de expansión mínima

ALGORITMO DE ÁRBOL DE EXPANSIÓN MÍNIMA
El algoritmo de árbol de expansión mínima enlaza los nodos de una red, en forma directa o indirecta, con la mínima longitud de las ramas enlazantes. Unaaplicación característica es en la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre dos poblaciones puede pasar por uno o más poblaciones adicionales. El diseño máseconómico del sistema de caminos indica que se minimice la distancia total de caminos pavimentados, resultado que se obtiene implementando el algoritmo de árbol de expansión mínima.
Los pasos delprocedimiento son los siguientes. Sea N = {1, 2, .., n} el conjunto de nodos de la red, y se definen
Ck = Conjunto de nodos que se han conectado en forma permanente en la iteración k
= Conjunto de nodosque todavía se deben conectar en forma permanente
Paso 0. El conjunto
Paso 1. Comenzar con cualquier nodo en el conjunto no conectado (o “inconexo”), e igualar con lo que Igualar k = 2.Paso general k. seleccionar un nodo j* en el conjunto no conectado Enlazar a j* en forma permanente con y sacarlo de esto es

Si el conjunto de nodos no conectados es vacío, detenerse.En cualquier otro caso, igualar k = k + 1 y repetir el paso.
Ejemplo 6.2.1
Midwest TV Cable Company esta en el proceso de proporcionar servicio de cable a cinco nuevas áreas habitacionales. Lafigura 6.4 representa los enlaces posibles de TV entre las cinco áreas. Las millas de cable se muestran en cada arco. Determine la red de cable más económica. El algoritmo comienza en el nodo 1 (cualquierotro nodo podría ser), con lo que se obtiene

Las iteraciones del algoritmo se resumen en la figura 6.5. los arcos con línea delgada son todos los enlaces posibles entre c y . las ramasgruesas representan los enlaces permanentes entre los nodos del conjunto conectado (o “conexo”) C, y la rama con línea interrumpida representa el nuevo enlace (permanente) que se agrega en cada...