Algoritmo de árbol mínimo de Sollin

Question

Sí, esta es la tarea. Me preguntaba si alguien podría explicar el proceso del algoritmo de Sollin (o Borůvka) para determinar un árbol de expansión mínimo. Además, si pudiera explicar cómo determinar el número de iteraciones en el peor de los casos, sería genial.

Answer 1

En un nivel superior, el algoritmo funciona de la siguiente manera:

• Mantenga que tiene una serie de árboles que abarcan algunas subgrafías. Inicialmente, cada vértice del gráfico es un MST sin bordes.
• En cada iteración, para cada uno de sus árboles de expansión, encuentre un borde más barato que lo conecte a otro árbol de expansión. (Esta es una simplificación).

El peor de los casos en términos de iteraciones es que siempre fusiona pares de árboles. En ese caso, el número de árboles que tiene se reducirá a la mitad en cada iteración, por lo que el número de iteraciones es logarítmica en el número de nodos.

También tenga en cuenta que hay un truco especial involucrado en la elección de los bordes para agregar: si no tiene cuidado, puede introducir un círculo cuando el árbol A se conecta al árbol B, el árbol B se conecta al árbol C y el árbol C se conecta al árbol A. ( Esto solo puede suceder si los tres bordes elegidos tienen el mismo peso. El truco es tener un desempate arbitrario pero fijo, como un orden fijo de los bordes).

Así que allí, esa es mi descripción general de la tarjeta de índice.

Answer 2

Estoy usando la terminología del laico.

• Primero seleccione un vértice
• Verifique todos los bordes de ese vértice y seleccione uno con el peso mínimo
• Haga esto para todos los vértices (algunos bordes pueden seleccionarse más de una vez)
• Obtendrá componentes conectados.
• De estos componentes conectados seleccione un borde con un peso mínimo.

Se formará su árbol de expansión con un peso mínimo