El algoritmo de Borůvka

El algoritmo de Borůvka es un algoritmo voraz para encontrar un árbol de expansión mínima en un grafo, o un bosque de expansión mínima en el caso de un grafo no 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 sobre computación paralela .

El algoritmo comienza encontrando la arista de peso mínimo incidente a cada vértice del grafo y agregando todas esas aristas al bosque. Luego, repite un proceso similar para encontrar la arista de peso mínimo desde cada árbol construido hasta el momento a un árbol diferente, y agrega todas esas aristas al bosque. Cada repetición de este proceso reduce el número de árboles, dentro de cada componente conexa del grafo, a lo sumo la mitad de este valor anterior, por lo que después de un número logarítmico de repeticiones, el proceso finaliza. Cuando finaliza, el conjunto de aristas agregadas 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". La variable completada sirve para determinar si el bosque F es un bosque generador.

Si las aristas no tienen pesos distintos, se debe usar una regla de desempate consistente, por ejemplo, basada en algún orden total de vértices o aristas. Esto se puede lograr representando los vértices como enteros y comparándolos directamente; comparando sus direcciones de memoria ; etc. Una regla de desempate es necesaria para asegurar que el grafo creado sea realmente un bosque, es decir, que no contenga ciclos. Por ejemplo, consideremos 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 ordene las aristas primero por origen y luego por destino evitará la creación de un ciclo, dando 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 ). La salida es: F , un bosque de expansión mínima de G . Inicializa un bosque F a ( V , E ′ ) donde E ′ = {}. completado := falso mientras no completado hacer Encuentra las componentes conexas de F y asigna a cada vértice su componente Inicializa el borde más barato para cada componente a "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 is-preferred-over( 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 is-preferred-over( 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 "None" entonces // no se pueden fusionar más árboles -- hemos terminado completed := true else completed := false Para cada componente cuya arista más barata no sea "None" haga Agregue su arista más barata a E'.La función is-preferred-over( edge1 , edge2 ) es return ( edge2 es "None") o (peso( arista1 ) < peso( arista2 )) o (peso( arista1 ) = peso( arista2 ) y regla de desempate( arista1 , arista2 )) La función tie-breaking-rule( edge1 , edge2 ) es la regla de desempate; devuelve verdadero si y solo si edge1 es preferido sobre edge2 en caso de empate.

Como optimización, se podría eliminar de G cada arista que conecte 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 su terminación, y por lo tanto, se ejecuta en 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 E ≥ V ). En grafos planares , y más generalmente en familias de grafos cerrados bajo operaciones menores de grafos , se puede lograr que se ejecute en tiempo lineal, eliminando todas las aristas excepto la 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ínima aleatorio más rápido basado en parte en el algoritmo de Borůvka debido a Karger, Klein y Tarjan se ejecuta en tiempo esperado O( E ) . ^{[ 9 ]} El mejor algoritmo de árbol de expansión mínima (determinista) conocido por 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 de Ackermann inversa . ^{[ 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.