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.
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.
iteraciones en el bucle externo antes de terminar, y por lo tanto su complejidad temporal es
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
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