Algoritmo de Borůvka

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ínima 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. El algoritmo fue redescubierto por Choquet en 1938; nuevamente por Florek, Łukasiewicz, Perkal, Steinhaus y Zubrzycki en 1951; y nuevamente por Georges Sollin en 1965. Este algoritmo se denomina frecuentemente algoritmo de Sollin, especialmente en la literatura de computación paralela.

El algoritmo comienza por encontrar el borde de peso mínimo que incide en cada vértice del gráfico y agrega todos esos bordes al bosque. Luego, repite un proceso similar de encontrar el borde de peso mínimo de cada árbol construido hasta el momento 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, como máximo a la mitad de este valor anterior, entonces, después de muchas repeticiones logarítmicas, el proceso finaliza. Cuando lo hace, el conjunto de aristas que ha agregado forma el bosque de expansión mínimo.

Pseudocódigo

El siguiente pseudocódigo ilustra una implementación básica del algoritmo de Borůvka. En las cláusulas condicionales, cada borde uv se considera más barato que "Ninguno". El propósito de la variable completado es determinar si el bosque F es todavía un bosque expansivo.

Si los bordes no tienen pesos distintos, entonces se debe usar una regla de desempate consistente, p. basado en algún orden total en 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 grafo 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 borde de peso mínimo para {a}, bc para {b} y ca por {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}.

algoritmo Borůvka es entrada: Un gráfico no dirigido ponderado G =V, E).
 Producto: F, un bosque de lazo mínimo G.

Iniciar un bosque F a)V, E 'Donde E ' = {}.

 terminado:= falso mientras no terminado doEncontrar los componentes conectados F y asignar a cada vértice su componente
Inicia el borde más barato para cada componente a "None"
 para cada uno borde uv dentro E, donde u y v están en diferentes componentes F:
Deja wx ser el borde más barato para el componente de u si es-preferido-sobre(uv, wx) entoncesSet uv como el borde más barato para el componente de uDeja Yz ser el borde más barato para el componente de v si es-preferido-sobre(uv, Yz) entoncesSet uv como el borde más barato para el componente de v si todos los componentes tienen el borde más barato fijado para "None" entonces // no más árboles pueden ser fusionados - estamos acabados terminado:= verdadero más terminado:= falso para cada uno componente cuyo borde más barato no es "None" doAñadir su borde más barato a E 'función es-preferido-sobre(borde1, borde2) es retorno ()borde2 es "No") o
(peso)borde1) Peso(borde2) o
(peso)borde1) = pesoborde2) y la corbata rompe-rule(borde1, borde2)

función corbata que rompe la corbataborde1, borde2) esLa regla que rompe la corbata; devuelve verdadero si borde1es preferido sobre borde2 en el caso de una corbata.

Como optimización, se podría eliminar de G cada arista que se encuentra para conectar dos vértices en el mismo componente, para que no contribuya al tiempo de búsqueda de aristas más baratas en componentes posteriores.

Complejidad

Se puede demostrar que el algoritmo de Borůvka toma O(log V) iteraciones del ciclo externo hasta que termina y, por lo tanto, ejecutar 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 (suponiendo E ≥ V). En grafos planos, y más generalmente en familias de grafos cerrados bajo operaciones menores de grafos, se puede hacer que se ejecute en tiempo lineal, eliminando todo menos el borde más barato entre cada par de componentes después de cada etapa del algoritmo.

Ejemplo

Imagen	componentes	Descripción
	{A} {B} {C} {D} {E} {F} {G}	Este es nuestro gráfico original ponderado. Los números cercanos a los bordes indican su peso. Inicialmente, cada vértice por sí mismo es un componente (círculos azules).
	{A,B,D,F} {C,E,G}	En la primera iteración del bucle exterior se añade el límite mínimo de peso de cada componente. Algunos bordes se seleccionan dos veces (AD, CE). Quedan dos componentes.
	{A,B,C,D,E,F,G}	En la segunda y última iteración, se añade el límite mínimo de peso de cada uno de los dos componentes restantes. Esto es el mismo borde. Queda un componente y hemos terminado. El borde BD no se considera porque ambos puntos finales están en el mismo componente.

Otros algoritmos

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.

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 que Karger, Klein y Tarjan se ejecuta en O(E) esperado tiempo. El algoritmo de árbol de expansión mínimo más conocido (determinista) de Bernard Chazelle también se basa en parte en el de Borůvka y se ejecuta en O(E α( E,V)) tiempo, donde α es la inversa de la función de Ackermann. Estos algoritmos aleatorizados y deterministas combinan pasos del algoritmo de Borůvka, reduciendo el número de componentes que quedan por conectar, con pasos de otro tipo que reducen el número de aristas entre pares de componentes.