Algoritmo de Boruvka

El Algoritmo de Borůvka es un algoritmo para encontrar el árbol recubridor mínimo en un grafo ponderado en el que todos sus arcos tienen distinto peso.

Fue publicado por primera vez en 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 nuevo por 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.

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 en cuenta 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értices conectados como «componente», el pseudocódigo del Algoritmo de Boruvka es:

Con el Algoritmo de Boruvka se puede obtener una complejidad de ${displaystyle O(log(V))}$ iteraciones en el bucle externo antes de terminar, y por lo tanto su complejidad temporal es ${displaystyle O(Elog(V))}$, donde ${displaystyle E}$ es el número de arcos, y ${displaystyle V}$ es el número de vértices de ${displaystyle G}$. En grafos planos puede implementarse para ejecutarse en tiempo lineal, eliminando los arcos de menor peso entre cada par de nodos después de cada etapa del algoritmo.^[4]​

Entre otros algoritmos para este problema se incluyen el Algoritmo de Prim (realmente descubierto por Vojtech Jarnik) y el Algoritmo de Kruskal. Algoritmos más rápidos pueden ser obtenidos combinando el Algoritmo de Prim con el Algoritmo de Boruvka.

El algoritmo más rápido para hallar el árbol de recubrimiento mínimo aleatorio está basado en parte en el algoritmo de Boruvka gracias a Karger, Klein y Tarjan y se obtiene una complejidad ${displaystyle O(E)}$.

El mejor algoritmo (determinista) conocido para encontrar el árbol recubridor mínimo de Bernard Chazelle está también basado en parte en el Algoritmo de Boruvka y tiene complejidad temporal ${displaystyle O(Ealpha (V))}$, donde ${displaystyle alpha }$ es la inversa de la Función de Ackermann. Estos algoritmos aleatorios y deterministas combinan pasos del Algoritmo de Boruvka reduciendo el número de nodos que quedan por conectar, con pasos de diferente tipo que reduzcan el número de arcos entre cada par de nodos.