Calculadora Algoritmo de Boruvka

Pseudocódigo

Cada componente elige su propia arista saliente más barata, y todas esas elecciones se aplican a la vez. Rondas en lugar de pasos, que es lo que lo hace paralelizable.

Boruvka(grafo):
    hacerConjunto(v) para cada vértice
    mst = []

    mientras quede más de una componente:
        masBarata = {} // por componente
        para cada arista (u, v, w):
            a = buscar(u); b = buscar(v)
            si a == b: continuar        // arista interna
            si w < masBarata[a]: masBarata[a] = (u,v,w)
            si w < masBarata[b]: masBarata[b] = (u,v,w)

        para cada arista e en masBarata.valores():
            si buscar(e.u) != buscar(e.v):  // quizá ya unidas
                unir(e.u, e.v); mst.añadir(e)

La guarda del segundo bucle es esencial, no defensiva. Dos componentes eligen con frecuencia la misma arista, una desde cada extremo, y aplicarla dos veces añadiría un duplicado. La corrección exige que los pesos de las aristas sean distintos, o un criterio de desempate consistente como comparar identificadores: sin él, varias componentes pueden elegir cada una una arista distinta de igual peso y formar juntas un ciclo.

Ejemplo resuelto, paso a paso

Construye el árbol de expansión mínimo sobre el mismo grafo usado para Prim y Kruskal, de modo que puedan compararse los tres.

Grafo de ejemplo: Aristas no dirigidas A-B (2), A-C (3), B-C (1), C-D (4) y B-D (7).

1. Empezar. Cada vértice es su propia componente: {A}, {B}, {C}, {D}. Toda arista es, por tanto, saliente para sus dos extremos.
2. Cada componente elige. La componente A compara A-B con 2 frente a A-C con 3 y elige A-B. La componente B compara A-B con 2, B-C con 1 y B-D con 7, y elige B-C. La componente C compara A-C con 3, B-C con 1 y C-D con 4, y elige B-C. La componente D compara C-D con 4 frente a B-D con 7 y elige C-D.
3. Observa el duplicado. B y C propusieron ambas la misma arista B-C, una desde cada extremo. La guarda del segundo bucle la aplica una sola vez, que es exactamente por lo que existe esa comprobación.
4. Aplicar todas las elecciones a la vez. Añadir A-B, B-C y C-D fusiona todo en una sola componente en una única ronda. Son tres aristas para cuatro vértices, así que el árbol ya está completo.
5. El bucle termina. Solo queda una componente, así que no se ejecuta una segunda ronda.

El árbol de expansión mínimo es A-B, B-C y C-D con peso total 2 + 1 + 4 = 7, el mismo árbol que produjeron Prim y Kruskal. Boruvka llegó allí en una ronda en lugar de tres pasos secuenciales, y ese es el punto: cada ronda al menos reduce a la mitad el número de componentes, ya que toda componente se fusiona con al menos otra, de modo que nunca hacen falta más de O(log V) rondas.

Complejidad y de dónde sale

Tiempo: O(E log V) · Espacio: O(V + E)

Cada ronda recorre todas las aristas una vez con O(E) para hallar la arista saliente más barata por componente. Toda componente se fusiona con al menos otra durante una ronda, así que el número de componentes al menos se reduce a la mitad, lo que significa que ocurren a lo sumo log base 2 de V rondas. Multiplicando se obtiene O(E log V), igual que Prim y Kruskal. La propiedad distintiva es que dentro de una ronda cada componente trabaja de forma independiente, así que el recorrido se paraleliza directamente, y por eso Boruvka sustenta las implementaciones de MST en GPU y distribuidas mientras que Prim y Kruskal, inherentemente secuenciales, no. Los algoritmos híbridos ejecutan unas pocas rondas de Boruvka para encoger el grafo y luego cambian a Prim.

Cuándo usar Algoritmo de Boruvka y cuándo no

Los tres algoritmos clásicos de MST cuestan O(E log V). La diferencia es estructural.

Errores frecuentes

• No tratar los pesos empatados. Con pesos iguales, componentes distintas pueden elegir aristas distintas que juntas cierran un ciclo, y el resultado no es un árbol. Rompe los empates de forma consistente, por ejemplo por índice de arista, para que todas las componentes coincidan en un mismo orden. Con pesos distintos el problema desaparece.
• Añadir dos veces la misma arista. Dos componentes proponen habitualmente la misma arista desde extremos opuestos. Sin comprobar que los extremos siguen en componentes distintas en el momento de aplicarla, la arista se añade dos veces y el número de aristas supera V - 1.
• Recalcular componentes dentro del recorrido de aristas. Llamar a buscar repetidamente sin compresión de caminos encarece mucho cada ronda por encima de O(E). Usa Union-Find con compresión de caminos y unión por rango, exactamente igual que en Kruskal.
• Suponer que necesita un grafo conexo. Igual que Kruskal, Boruvka maneja de forma natural entradas desconectadas y devuelve un bosque de expansión mínimo. La condición del bucle debe ser entonces "ninguna componente tiene arista saliente" en lugar de "queda una componente", o no terminará.
• Pasar por alto que es anterior a los demás. Publicado en 1926 para planificar una red eléctrica en Moravia, Boruvka es el algoritmo de MST más antiguo que se conoce, anterior tanto a Prim como a Kruskal. Suele enseñarse el último, lo que oculta que la formulación paralela fue la primera en aparecer.

Preguntas frecuentes

¿Cómo funciona el algoritmo de Boruvka?

Cada componente selecciona simultáneamente la arista más barata que sale de ella, y todas las aristas seleccionadas se añaden a la vez, fusionando componentes. Esto se repite hasta que queda una sola componente. Como cada componente se fusiona con al menos otra por ronda, el número de componentes al menos se reduce a la mitad cada vez y solo hacen falta O(log V) rondas.

¿Cuál es la complejidad temporal del algoritmo de Boruvka?

O(E log V). Cada ronda recorre las E aristas para hallar la arista saliente más barata por componente, y ocurren a lo sumo log V rondas porque el número de componentes se reduce a la mitad en cada una. Esto iguala asintóticamente a Prim y Kruskal.

¿Por qué el algoritmo de Boruvka es bueno para computación paralela?

Porque dentro de una ronda cada componente determina su propia arista saliente más barata de forma independiente, sin estado compartido ni requisito de orden. Eso se traslada directamente a GPU y a clústeres distribuidos. Prim y Kruskal son inherentemente secuenciales: cada uno depende de la única decisión global tomada inmediatamente antes.

¿Por qué los pesos de las aristas deben ser distintos?

Con pesos empatados, componentes distintas pueden seleccionar aristas distintas de igual coste que juntas forman un ciclo, con lo que el resultado no es un árbol. Cualquier criterio de desempate consistente, como comparar índices de arista cuando los pesos coinciden, restaura la corrección. Los pesos distintos hacen además único el árbol de expansión mínimo.

¿Cuál es la diferencia entre Boruvka, Prim y Kruskal?

Los tres producen un árbol de expansión mínimo en O(E log V). Prim hace crecer un árbol desde un vértice inicial usando una cola de prioridad. Kruskal ordena todas las aristas y añade las que no cierran ciclo. Boruvka hace que cada componente elija su arista saliente más barata en rondas paralelas, y es el único de los tres que se paraleliza de forma natural.