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 un 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 frecuentemente algoritmo de Sollin , especialmente en la literatura de computación paralela .
El algoritmo comienza encontrando la arista de peso mínimo incidente en cada vértice del grafo y agregando todas esas aristas al bosque. Luego, repite un proceso similar de encontrar la arista de peso mínimo de cada árbol construido hasta el momento en un árbol diferente y agregando todas esas aristas al bosque. Cada repetición de este proceso reduce el número de árboles, dentro de cada componente conectado del grafo, a la mitad de este valor anterior como máximo, por lo que después de muchas repeticiones logarítmicas, el proceso termina. Cuando lo hace, el conjunto de aristas que ha agregado forma el bosque de expansión mínima.
El siguiente pseudocódigo ilustra una implementación básica del algoritmo de Borůvka. En las cláusulas condicionales, cada arista uv se considera más barata que "Ninguna". El propósito de la variable completada es determinar si el bosque F todavía es un bosque expansivo.
Si las aristas no tienen pesos distintos, entonces se debe utilizar una regla de desempate consistente, por ejemplo, basada en algún orden total en vértices o aristas. Esto se puede lograr representando vértices como números enteros y comparándolos directamente; comparando sus direcciones de memoria ; etc. Una regla de desempate es necesaria para asegurar que el grafo creado es de hecho un bosque, es decir, no contiene ciclos. Por ejemplo, considere un grafo triangular con nodos { a , b , c } y todas las aristas de peso 1. Entonces se podría crear un ciclo si seleccionamos ab como la arista de peso mínimo para { a }, bc para { b } y ca para { c }. Una regla de desempate que ordena las aristas primero por origen, luego por destino, evitará la creación de un ciclo, lo que dará como resultado el árbol de expansión mínimo { ab , bc }.
El algoritmo Borůvka tiene como entrada: un grafo no dirigido ponderado G = ( V , E ). Salida: F , un bosque de expansión mínimo de G . Inicializar un bosque F a ( V , E ′ ) donde E ′ = {}. completado := false mientras no completado do Encuentra los componentes conectados de F y asigna a cada vértice su componente Inicialice el borde más barato para cada componente en "Ninguno" para cada arista uv en E , donde u y v están en diferentes componentes de F : sea wx la arista más barata para el componente de u si es-preferido-sobre( uv , wx ) entonces Establezca uv como la arista más barata para el componente de u sea yz la arista más barata para el componente de v si es-preferido-sobre( uv , yz ) entonces Establezca uv como la arista más barata para el componente de v si todos los componentes tienen la arista más barata establecida en "Ninguno" entonces // no se pueden fusionar más árboles -- hemos terminado completado := verdadero de lo contrario completado := falso para cada componente cuya arista más barata no sea "Ninguno" agregar su arista más barata a E'La función is-preferred-over( edge1 , edge2 ) retorna ( edge2 es "Ninguno") o (peso( borde1 ) < peso( borde2 )) o (peso( borde1 ) = peso( borde2 ) y regla de desempate( borde1 , borde2 ))función tie-breaking-rule( edge1 , edge2 ) es la regla de desempate; devuelve verdadero si y solo si se prefiere edge1 sobre edge2 en caso de empate.
Como optimización, se podría eliminar de G cada arista que se encuentre que conecta dos vértices en el mismo componente, de modo que no contribuya al tiempo de búsqueda de las aristas más baratas en componentes posteriores.
Se puede demostrar que el algoritmo de Borůvka requiere O (log V ) iteraciones del bucle externo hasta que termina y, por lo tanto, se ejecuta en un tiempo O ( E log V ) , donde E es el número de aristas y V es el número de vértices en G (suponiendo que E ≥ V ). En grafos planos y, más generalmente, en familias de grafos cerrados bajo operaciones de grafos menores , se puede hacer que se ejecute en tiempo lineal, eliminando todos los componentes excepto la arista más barata 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 Borůvka y se ejecuta en el 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 un tipo diferente que reducen el número de aristas entre pares de componentes.