El algoritmo de Borůvka es un algoritmo codicioso para encontrar un árbol de expansión mínimo en un gráfico, o un bosque de expansión mínimo en el caso de un gráfico que no está conectado.
Fue publicado por primera vez en 1926 por Otakar Borůvka como método para construir una red eléctrica eficiente para Moravia . [1] [2] [3] El algoritmo fue redescubierto por Choquet en 1938; [4] nuevamente por Florek, Łukasiewicz , Perkal, Steinhaus y Zubrzycki en 1951; [5] y nuevamente por Georges Sollin en 1965. [6] Este algoritmo se denomina con frecuencia algoritmo de Sollin , especialmente en la literatura sobre computación paralela .
El algoritmo comienza encontrando el borde de peso mínimo incidente en cada vértice del gráfico y agregando todos esos bordes al bosque. Luego, repite un proceso similar de encontrar el borde de peso mínimo de cada árbol construido hasta ahora en un árbol diferente y agregar todos esos bordes al bosque. Cada repetición de este proceso reduce el número de árboles, dentro de cada componente conectado del gráfico, a como máximo la mitad de este valor anterior, por lo que después de muchas repeticiones logarítmicas el proceso finaliza. Cuando lo hace, el conjunto de bordes que ha agregado forma el bosque de extensión mínima.
El siguiente pseudocódigo ilustra una implementación básica del algoritmo de Borůvka. En las cláusulas condicionales, cada ventaja uv se considera más barata que "Ninguna". El propósito de la variable completa es determinar si el bosque F es todavía un bosque expansivo.
Si las aristas no tienen pesos distintos, entonces se debe utilizar una regla de desempate coherente, por ejemplo, basada en algún orden total en los vértices o aristas. Esto se puede lograr representando los vértices como números enteros y comparándolos directamente; comparar sus direcciones de memoria ; etc. Es necesaria una regla de desempate para garantizar que el gráfico creado sea realmente un bosque, es decir, que no contenga ciclos. Por ejemplo, considere un gráfico triangular con nodos { a , b , c } y todos los bordes de peso 1. Entonces se podría crear un ciclo si seleccionamos ab como el borde de peso mínimo para { a }, bc para { b } y ca para { c }. Una regla de desempate que ordene los bordes primero por origen y luego por destino evitará la creación de un ciclo, lo que dará como resultado el árbol de expansión mínimo { ab , bc }.
Se introduce el algoritmo de Borůvka : un gráfico no dirigido ponderado G = ( V , E ). salida: F , un bosque de extensión mínima de G . Inicialice un bosque F en ( V , E ′ ) donde E ′ = {}. completado := false mientras no esté completado encuentre los componentes conectados de F y asigne a cada vértice su componente Inicialice el borde más barato para cada componente en "Ninguno" para cada borde uv en E , donde u y v están en diferentes componentes de F : sea wx el borde más barato para el componente de u si se prefiere sobre ( uv , wx ) , luego establezca uv como el borde más barato para el componente de u , sea yz el borde más barato para el componente de v si se prefiere over( uv , yz ) luego establezca uv como el borde más barato para el componente de v si todos los componentes tienen el borde más barato establecido en "Ninguno" entonces // no se pueden fusionar más árboles; hemos terminado : = verdadero , de lo contrario se completó : = falso para cada componente cuyo borde más barato no sea "Ninguno" Agregue su borde más barato a E'la función se prefiere sobre ( borde1 , borde2 ) es devuelta ( borde2 es "Ninguno") o (peso ( borde1 ) <peso ( borde2 )) o (peso ( borde1 ) = peso ( borde2 ) y regla de desempate ( borde1 , borde2 ))la función regla de desempate ( borde1 , borde2 ) es la regla de desempate; devuelve verdadero si y sólo si se prefiere el borde1 sobre el borde2 en el caso de un empate.
Como optimización, se podría eliminar de G cada arista que conecta dos vértices en el mismo componente, de modo que no contribuya al tiempo de búsqueda de aristas más baratas en componentes posteriores.
Se puede demostrar que el algoritmo de Borůvka toma O (log V ) iteraciones del bucle externo hasta que termina y, por lo tanto, se ejecuta en el tiempo O ( E log V ) , donde E es el número de aristas y V es el número de vértices en G (asumiendo E ≥ V ). En gráficos planos , y más generalmente en familias de gráficos cerrados bajo operaciones menores de gráficos , se puede hacer que se ejecute en tiempo lineal, eliminando todos los bordes, excepto el más barato, entre cada par de componentes después de cada etapa del algoritmo. [7]
Otros algoritmos para este problema incluyen el algoritmo de Prim y el algoritmo de Kruskal . Se pueden obtener algoritmos paralelos rápidos combinando el algoritmo de Prim con el de Borůvka. [8]
Un algoritmo de árbol de expansión mínimo aleatorio más rápido basado en parte en el algoritmo de Borůvka debido a Karger, Klein y Tarjan se ejecuta en el tiempo esperado O ( E ) . [9] El algoritmo de árbol de expansión mínimo (determinista) más conocido de Bernard Chazelle también se basa en parte en el de Borůvka y se ejecuta en tiempo O( E α( E , V )) , donde α es la función inversa de Ackermann . [10] Estos algoritmos aleatorios y deterministas combinan pasos del algoritmo de Borůvka, reduciendo el número de componentes que quedan por conectar, con pasos de diferente tipo que reducen el número de aristas entre pares de componentes.