Algoritmo de Boruvka (Algoritmo de Sollin)

Puedes opinar sobre este contenido:
  • 0
  • 0
  • 0
  • 0

Actualizado el 3 de enero de 2022, por Luis Benites.

¿Qué es el algoritmo de Boruvka?

El algoritmo de Boruvka es una forma de encontrar un árbol de expansión mínimo , un árbol de expansión donde se minimiza la suma de los pesos de los bordes. Fue el primer algoritmo desarrollado (en 1926) para encontrar MST; Otakar Boruvka lo usó para encontrar la ruta más eficiente para una red eléctrica.

Hay muchas formas de encontrar árboles de expansión mínimos. El algoritmo de Boruvka es un algoritmo codicioso y es similar al algoritmo de Kruskal y al algoritmo de Prim . Es básicamente un cruce entre los dos algoritmos. También se le conoce como algoritmo de Sollin , especialmente en informática.

Ejemplo del algoritmo de Boruvka

Encuentre el árbol de expansión mínimo para el siguiente gráfico usando el Algoritmo de Buruvka. Paso 1: Escriba una lista de componentes. Para este gráfico tenemos: A,B,C,D,E,F,G,H,I,J,K,L. Este paso es opcional pero le ayuda a realizar un seguimiento.
algoritmo de boruvka

Paso 2: Resalte el borde saliente más barato para cada nodo en su lista. Por ejemplo, el nodo A tiene bordes salientes con pesos 1 y 7, por lo que resaltaremos 1. Continúe secuencialmente (para esta lista, vaya a B, luego a C…).
Directrices :

  1. En esta etapa, solo resalte un borde más barato para cada nodo.
  2. Para un empate (el nodo E tiene dos aristas con un peso de 4), asigne un peso menor a una de las aristas. Esto es arbitrario, pero debe permanecer constante durante todo el proceso. Para este ejemplo, haré que el borde de la izquierda tenga el peso más bajo.
  3. Resalte siempre el borde más barato, incluso si se ha resaltado antes . ¡No elija el borde con el siguiente peso más bajo! A efectos prácticos, esto significa que es posible que no tenga que resaltar nada para algunos nodos, si ya se ha resaltado el peso más bajo.

algoritmo de boruvka 2
Paso 3: Resalte los grupos de árboles separados. Estos son los conjuntos de nodos conectados, a los que llamaremos componentes . Paso 4: Repita el algoritmo para cada componente (cada conjunto de color diferente). Esta vez, para cada nodo, elija el borde más barato fuera del componente . Por ejemplo, ABCDHL es un componente (nodos azules). Para el nodo A, el borde más barato fuera del componente es el nodo 7 (porque el nodo 1 está conectado dentro del componente). Estoy resaltando en azul para mayor claridad: puedes usar el color que quieras. Directrices :
algoritmo de boruvka 3

  1. Asegúrese de elegir el borde más barato fuera del componente. Para este gráfico y esta iteración, esos bordes están coloreados en negro.
  2. Como en la primera iteración, omita resaltar un borde si ya se ha resaltado esta vez.

algoritmo de boruvka 4
Paso 5: si todos sus nodos están conectados en un solo componente, ya está. Si no, repita el paso 4.

El siguiente gráfico muestra el MST final. He borrado los bordes no utilizados (negros).
algoritmo de boruvka 6

Redactor del artículo

  • Luis Benites
    Director de Statologos.com

    Tengo una Maestría en Ciencias en Estadística Aplicada y he trabajado en algoritmos de aprendizaje automático para empresas profesionales tanto en el sector de la salud como en el comercio minorista.

    Ver todas las entradas

¿Te hemos ayudado?

Ayudanos ahora tú, dejanos un comentario de agradecimiento, nos ayuda a motivarnos y si te es viable puedes hacer una donación:

La ayuda no cuesta nada

Por otro lado te rogamos que compartas nuestro sitio con tus amigos, compañeros de clase y colegas, la educación de calidad y gratuita debe ser difundida, recuerdalo:

Deja un comentario

Distribución unimodal: descripción general Una distribución unimodal es una distribución con un pico claro o el valor más frecuente. Los…
statologos comunidad-2

Compartimos información EXCLUSIVA y GRATUITA solo para suscriptores (cursos privados, programas, consejos y mucho más)

You have Successfully Subscribed!