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 es frecuentemente llamado algoritmo de Sollin , especialmente en la literatura de 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, como máximo a la mitad de este valor anterior, por lo que después de muchas repeticiones logarítmicamente, el proceso finaliza. Cuando lo hace, el conjunto de bordes que ha agregado forma el bosque de expansión mínimo.
Pseudocódigo
Al designar cada vértice o conjunto de vértices conectados como un " componente ", el pseudocódigo para el algoritmo de Borůvka es:
algoritmo Borůvka es de entrada: Un gráfico G cuyos bordes tienen pesos distintos. Salida: F es el bosque de expansión mínimo de G . Inicialice un bosque F para que sea un conjunto de árboles de un vértice, uno para cada vértice del gráfico. completado = falso mientras no completó do Encuentra los componentes conectados de F y la etiqueta de cada vértice de G por su componente Inicialice la ventaja más barata para cada componente en "Ninguno" para cada borde ultravioleta del G hacer si u y v tienen diferentes etiquetas de los componentes: si ultravioleta es más barato que el borde más barata para el componente de u luego Conjunto UV como el borde más barata para el componente de u si ultravioleta es más barato que el borde más barata para el componente de v luego Conjunto UV como el borde más barata para el componente de v completado = verdadera para cada componente cuyo borde más barata no es "Ninguno" no Añadir su borde más barata de F completó = falsa
En las cláusulas condicionales, cada borde uv se considera más barato que "Ninguno". El propósito de la variable completada es determinar si el bosque F es todavía un bosque expansivo. Si los bordes no tienen pesos distintos, entonces se puede utilizar una regla de ruptura de empates consistente (por ejemplo, romper los lazos por los identificadores de objeto de los bordes).
Una optimización (no necesaria para el análisis) es eliminar de G cada borde que se encuentra para conectar dos vértices en el mismo componente entre sí.
Complejidad
Se puede demostrar que el algoritmo de Borůvka toma O (log V ) iteraciones del bucle exterior 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 . En gráficas planas , y más generalmente en familias de gráficas cerradas bajo operaciones menores de gráficas , 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. [7]
Ejemplo
Imagen | componentes | Descripción |
---|---|---|
{A} {B} {C} {D} {E} {F} {G} | Este es nuestro gráfico ponderado original. Los números cerca de 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 externo, se agrega el borde de peso mínimo de cada componente. Algunas aristas se seleccionan dos veces (AD, CE). Quedan dos componentes. | |
{A, B, C, D, E, F, G} | En la segunda y última iteración, se agrega el borde de peso mínimo de cada uno de los dos componentes restantes. Estos resultan ser el mismo borde. Queda un componente y hemos terminado. El borde BD no se considera porque ambos extremos 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 rápidos en paralelo 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 que Karger, Klein y Tarjan se ejecuta en el tiempo O ( E ) esperado . [9] 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 tiempo O ( E α ( E , V )) , donde α es la inversa de la función 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.
Notas
- ↑ Borůvka, Otakar (1926). "O jistém problému minimálním" [Acerca de cierto problema mínimo]. Práce Mor. Přírodověd. Spol. V Brně III (en checo y alemán). 3 : 37–58.
- ^ Borůvka, Otakar (1926). "Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribución a la solución de un problema de construcción económica de redes eléctricas)". Elektronický Obzor (en checo). 15 : 153-154.
- ^ Nešetřil, Jaroslav ; Milková, Eva; Nešetřilová, Helena (2001). "Otakar Borůvka sobre el problema del árbol de expansión mínimo: traducción de ambos artículos de 1926, comentarios, historia". Matemáticas discretas . 233 (1-3): 3-36. doi : 10.1016 / S0012-365X (00) 00224-7 . hdl : 10338.dmlcz / 500413 . Señor 1825599 .
- ^ Choquet, Gustave (1938). "Étude de certains réseaux de route". Comptes Rendus de l'Académie des Sciences (en francés). 206 : 310–313.
- ^ Florek, K .; Łukaszewicz, J .; Perkal, J .; Steinhaus, Hugo ; Zubrzycki, S. (1951). "Sur la liaison et la division des points d'un ensemble fini" . Coloquio Mathematicae (en francés). 2 : 282-285. Señor 0048832 .
- ^ Sollin, Georges (1965). "Le tracé de canalisation". Redes de programación, juegos y transporte (en francés).
- ^ Eppstein, David (1999). "Abarcando árboles y llaves". En Sack, J.-R. ; Urrutia, J. (eds.). Manual de geometría computacional . Elsevier. págs. 425–461.; Mareš, Martin (2004). "Dos algoritmos de tiempo lineal para MST en clases de gráficos cerrados menores" (PDF) . Archivum Mathematicum . 40 (3): 315–320..
- ^ Bader, David A .; Cong, Guojing (2006). "Algoritmos rápidos de memoria compartida para calcular el bosque de expansión mínimo de gráficos dispersos". Revista de Computación Paralela y Distribuida . 66 (11): 1366-1378. CiteSeerX 10.1.1.129.8991 . doi : 10.1016 / j.jpdc.2006.06.001 .
- ^ Karger, David R .; Klein, Philip N .; Tarjan, Robert E. (1995). "Un algoritmo de tiempo lineal aleatorio para encontrar árboles de expansión mínimos". Revista de la ACM . 42 (2): 321–328. CiteSeerX 10.1.1.39.9012 . doi : 10.1145 / 201019.201022 .
- ^ Chazelle, Bernard (2000). "Un algoritmo de árbol de expansión mínimo con complejidad de tipo Ackermann inverso" (PDF) . J. ACM . 47 (6): 1028–1047. CiteSeerX 10.1.1.115.2318 . doi : 10.1145 / 355541.355562 .