SISTEMAS DE TOMA DE DECISIONES

El Algoritmo de Borůvka es un algoritmo para encontrar el mínimo árbol de expansión en un grafo ponderado en el que todos sus arcos tienen distinto peso.
Fue publicado por primera vezen 1926 por Otakar Borůvka como un método eficiente para construir la red eléctrica de Moravia.1 2 El algoritmo fue redescubierto por Choquet en 1938;3 de nuevopor Florek, Łukasiewicz, Perkal, Steinhaus y Zubrzycki en 1951; y de nuevo por Sollin a principio de la década de 1960. Debido a que Sollin fue el único de ellos que era científico en computación, este algoritmo es frecuentemente llamado Algoritmo de Sollin,especialmente en la literatura sobre computación paralela.

ALGORITMO
El algoritmo comienza examinando cada vértice y añadiendo el arco de menor peso desde ese vértice a otro en el grafo, sin tener encuenta los arcos ya agregados, y continua uniendo estos grupos de la misma manera hasta que se completa un árbol que cubra todos los vértices. Si denominamos a cada vértice o conjunto de vérticesconectados como «componente», el pseudocódigo del Algoritmo de Boruvka es:
Comenzar con un grafo conexo G en el que todos sus arcos tengan distinto peso, y un conjunto vacío de arcos T.
Mientras losvértices de G conectados por T sean disjuntos:
Crear un conjunto vacío de arcos S
Para cada componente:
Crear un conjunto vacío de arcos S
Para cada vértice v en el componente:
Agregar el arco demenor peso desde el vértice v a otro vértice en un componente disjunto a S
Añadir el arco de menor peso en S a E
Añadir el conjunto resultante E a T.
El conjunto de aristas resultante T es el árbol deexpansión mínimo de G.

COMPLEJIDAD
Con el Algoritmo de Boruvka se puede obtener una complejidad de  iteraciones en el bucle externo antes de terminar, y por lo tanto su complejidad temporal es ,donde  es el número de arcos, y  es el número de vértices de . En grafos planos puede implementarse para ejecutarse en tiempo lineal, eliminando los arcos de menor peso entre cada par de...