Algoritmo de Kruskal - Kruskal's algorithm

El algoritmo de Kruskal encuentra un bosque de expansión mínimo de un gráfico ponderado por bordes no dirigido . Si el gráfico está conectado , encuentra un árbol de expansión mínimo . (Un árbol de expansión mínimo de un gráfico conectado es un subconjunto de los bordes que forma un árbol que incluye todos los vértices , donde se minimiza la suma de los pesos de todos los bordes del árbol. Para un gráfico desconectado, un bosque de expansión mínimo es compuesto por un árbol de expansión mínimo para cada componente conectado .) Es un algoritmo codicioso en la teoría de grafos, ya que en cada paso agrega el siguiente borde de menor peso que no formará un ciclo al bosque de expansión mínimo.

Este algoritmo apareció por primera vez en Proceedings of the American Mathematical Society , págs. 48–50 en 1956, y fue escrito por Joseph Kruskal .

Otros algoritmos para este problema incluyen el algoritmo de Prim , el algoritmo inverso de eliminación , y el algoritmo de Borůvka .

Algoritmo

• crear un bosque F (un conjunto de árboles), donde cada vértice en el gráfico es un árbol separado
• crear un conjunto S que contenga todas las aristas del gráfico
• mientras que S no está vacío y F aún no abarca
  • quitar un borde con un peso mínimo de S
  • si el borde eliminado conecta dos árboles diferentes, agréguelo al bosque F , combinando dos árboles en un solo árbol

Al finalizar el algoritmo, el bosque forma un bosque de expansión mínimo del gráfico. Si el gráfico está conectado, el bosque tiene un solo componente y forma un árbol de expansión mínimo.

Pseudocódigo

Una demostración del algoritmo de Kruskal en un gráfico completo con pesos basados ​​en la distancia euclidiana.

El siguiente código se implementa con una estructura de datos de conjuntos disjuntos . Aquí, representamos nuestro bosque F como un conjunto de bordes y usamos la estructura de datos de conjuntos disjuntos para determinar de manera eficiente si dos vértices son parte del mismo árbol.

algorithm Kruskal(G) is
    F:= ∅
    for each v ∈ G.V do
        MAKE-SET(v)
    for each (u, v) in G.E ordered by weight(u, v), increasing do
        if FIND-SET(u) ≠ FIND-SET(v) then
            F:= F ∪ {(u, v)} ∪ {(v, u)}
            UNION(FIND-SET(u), FIND-SET(v))
    return F

Complejidad

Para un gráfico con bordes E y vértices V , se puede demostrar que el algoritmo de Kruskal se ejecuta en tiempo O ( E log E ), o equivalentemente, tiempo O ( E log V ), todo con estructuras de datos simples. Estos tiempos de ejecución son equivalentes porque:

• E es como máximo y . ${\ Displaystyle V ^ {2}}$${\ Displaystyle \ log V ^ {2} = 2 \ log V \ in O (\ log V)}$
• Cada vértice aislado es un componente independiente del bosque de extensión mínimo. Si ignoramos los vértices aislados obtenemos V ≤ 2 E , por lo que log V es . ${\ Displaystyle O (\ log E)}$

Podemos lograr este límite de la siguiente manera: primero clasifique los bordes por peso usando una clasificación de comparación en el tiempo O ( E log E ); esto permite que el paso "quitar un borde con peso mínimo de S " funcione en tiempo constante. A continuación, usamos una estructura de datos de conjuntos disjuntos para realizar un seguimiento de qué vértices están en qué componentes. Colocamos cada vértice en su propio conjunto disjunto, que toma operaciones O ( V ). Finalmente, en el peor de los casos, necesitamos iterar a través de todos los bordes, y para cada borde necesitamos hacer dos operaciones de 'búsqueda' y posiblemente una unión. Incluso una simple estructura de datos de conjuntos disjuntos, como los bosques de conjuntos disjuntos con unión por rango, puede realizar operaciones O ( E ) en tiempo O ( E log V ). Por tanto, el tiempo total es O ( E log E ) = O ( E log V ).

Siempre que las aristas ya estén ordenadas o se puedan ordenar en tiempo lineal (por ejemplo, con ordenación por conteo o ordenación por base ), el algoritmo puede usar una estructura de datos de conjuntos disjuntos más sofisticada para ejecutarse en tiempo O ( E α ( V )) , donde α es la inversa de crecimiento extremadamente lento de la función de Ackermann de un solo valor .

Ejemplo

Imagen	Descripción
	AD y CE son los bordes más cortos, con una longitud de 5, y AD se ha elegido arbitrariamente , por lo que se resalta.
	CE es ahora el borde más corto que no forma un ciclo, con una longitud de 5, por lo que se resalta como el segundo borde.
	El siguiente borde, DF con longitud 6, se resalta utilizando prácticamente el mismo método.
	Los siguientes bordes más cortos son AB y BE , ambos con longitud 7. AB se elige arbitrariamente y se resalta. El borde BD se ha resaltado en rojo, porque ya existe un camino (en verde) entre B y D , por lo que formaría un ciclo ( ABD ) si se eligiera.
	El proceso continúa resaltando el siguiente borde más pequeño, BE con longitud 7. Muchos más bordes se resaltan en rojo en esta etapa: BC porque formaría el bucle BCE , DE porque formaría el bucle DEBA y FE porque lo haría formulario FEBAD .
	Finalmente, el proceso termina con el borde EG de longitud 9, y se encuentra el árbol de expansión mínimo.

Prueba de corrección

La prueba consta de dos partes. Primero, se demuestra que el algoritmo produce un árbol de expansión . En segundo lugar, se demuestra que el árbol de expansión construido tiene un peso mínimo.

Árbol de expansión

Sea un gráfico ponderado conectado y sea ​​el subgráfico de producido por el algoritmo. no puede tener un ciclo, ya que, por definición, no se agrega un borde si da como resultado un ciclo. no se puede desconectar, ya que el algoritmo habría agregado el primer borde encontrado que une dos componentes de . Por lo tanto, es un árbol de expansión de . ${\ Displaystyle G}$${\ Displaystyle Y}$${\ Displaystyle G}$${\ Displaystyle Y}$${\ Displaystyle Y}$${\ Displaystyle Y}$${\ Displaystyle Y}$${\ Displaystyle G}$

Minimidad

Demostramos que la siguiente proposición P es verdadera por inducción : si F es el conjunto de bordes elegidos en cualquier etapa del algoritmo, entonces hay un árbol de expansión mínimo que contiene F y ninguno de los bordes rechazado por el algoritmo.

• Claramente, P es verdadera al principio, cuando F está vacío: cualquier árbol de expansión mínimo servirá, y existe uno porque un gráfico conectado ponderado siempre tiene un árbol de expansión mínimo.
• Supongamos ahora P es cierto para algunos borde conjunto no final F y dejar que T sea un árbol de expansión mínimo que contiene F .
  • Si la siguiente arista elegida e también está en T , entonces P es verdadera para F + e .
  • De lo contrario, si e no está en T entonces T + e tiene un ciclo C . Este ciclo contiene bordes que no pertenecen a F , ya que e no forma un ciclo cuando se añade a F , pero lo hace en T . Sea f una arista que está en C pero no en F + e . Tenga en cuenta que f también pertenece a T , y por P no ha sido considerado por el algoritmo. Por tanto, f debe tener un peso al menos tan grande como e . Entonces T - f + e es un árbol, y tiene el mismo peso o menos como T . Entonces T - f + e es un árbol de expansión mínimo que contiene F + e y nuevamente P se mantiene.
• Por lo tanto, según el principio de inducción, P se cumple cuando F se ha convertido en un árbol de expansión, lo cual solo es posible si F es un árbol de expansión mínimo.

Algoritmo paralelo

El algoritmo de Kruskal es inherentemente secuencial y difícil de paralelizar. Sin embargo, es posible realizar la clasificación inicial de los bordes en paralelo o, alternativamente, utilizar una implementación paralela de un montón binario para extraer el borde de peso mínimo en cada iteración. Como la clasificación en paralelo es posible en el tiempo en los procesadores, el tiempo de ejecución del algoritmo de Kruskal se puede reducir a O ( E α ( V )), donde α nuevamente es la inversa de la función de Ackermann de un solo valor . ${\ Displaystyle O (n)}$${\ Displaystyle O (\ log n)}$

Una variante del algoritmo de Kruskal, denominada Filter-Kruskal, ha sido descrita por Osipov et al. y es más adecuado para la paralelización. La idea básica detrás de Filter-Kruskal es dividir los bordes de una manera similar a la clasificación rápida y filtrar los bordes que conectan los vértices del mismo árbol para reducir el costo de clasificación. El siguiente pseudocódigo demuestra esto.

function filter_kruskal(G) is
    if |G.E| < kruskal_threshold:
        return kruskal(G)
    pivot = choose_random(G.E)
    ${\displaystyle E_{\leq }}$, ${\displaystyle E_{>}}$ = partition(G.E, pivot)
    A = filter_kruskal(${\displaystyle E_{\leq }}$)
    ${\displaystyle E_{>}}$ = filter(${\displaystyle E_{>}}$)
    A = A ∪ filter_kruskal(${\displaystyle E_{>}}$)
    return A

function partition(E, pivot) is
    ${\displaystyle E_{\leq }}$ = ∅, ${\displaystyle E_{>}}$ = ∅
    foreach (u, v) in E do
        if weight(u, v) <= pivot then
            ${\displaystyle E_{\leq }}$ = ${\displaystyle E_{\leq }}$ ∪ {(u, v)}
        else
            ${\displaystyle E_{>}}$ = ${\displaystyle E_{>}}$ ∪ {(u, v)}
    return ${\displaystyle E_{\leq }}$, ${\displaystyle E_{>}}$

function filter(E) is
    ${\displaystyle E_{\text{filtered}}}$ = ∅
    foreach (u, v) in E do
        if find_set(u) ≠ find_set(v) then
            ${\displaystyle E_{\text{filtered}}}$ = ${\displaystyle E_{\text{filtered}}}$ ∪ {(u, v)}
    return ${\displaystyle E_{\text{filtered}}}$

Filter-Kruskal se presta mejor para la paralelización, ya que la clasificación, el filtrado y la partición se pueden realizar fácilmente en paralelo mediante la distribución de los bordes entre los procesadores.

Finalmente, se han explorado otras variantes de una implementación paralela del algoritmo de Kruskal. Los ejemplos incluyen un esquema que usa hilos auxiliares para eliminar bordes que definitivamente no son parte del MST en segundo plano, y una variante que ejecuta el algoritmo secuencial en p subgrafos, luego fusiona esos subgrafos hasta que solo queda uno, el MST final.

Ver también

• Algoritmo de Prim
• Algoritmo de Dijkstra
• Algoritmo de Borůvka
• Algoritmo de eliminación inversa
• Agrupación en clústeres de enlace único
• Llave geométrica codiciosa

Referencias

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN   0-262-03293-7 . Sección 23.2: Los algoritmos de Kruskal y Prim, págs. 567–574.
• Michael T. Goodrich y Roberto Tamassia . Estructuras de datos y algoritmos en Java , cuarta edición. John Wiley & Sons, Inc., 2006. ISBN   0-471-73884-0 . Sección 13.7.1: Algoritmo de Kruskal, págs. 632 ..

enlaces externos

• Datos para el ejemplo del artículo .
• Complemento Gephi para calcular el código fuente de un árbol de expansión mínimo .
• Algoritmo de Kruskal con ejemplo y programa en c ++
• Código del algoritmo de Kruskal en C ++ aplicado a números aleatorios
• Código del algoritmo de Kruskal en Python con explicación