Algoritmo de Kruskal

El algoritmo de Kruskal ^[1] encuentra un bosque de expansión mínimo de un grafo no dirigido con ponderación de aristas . Si el grafo es conexo , encuentra un árbol de expansión mínimo . Es un algoritmo voraz que en cada paso agrega al bosque la arista de menor peso que no formará un ciclo . ^[2] Los pasos clave del algoritmo son la ordenación y el uso de una estructura de datos de conjunto disjunto para detectar ciclos. Su tiempo de ejecución está dominado por el tiempo para ordenar todas las aristas del grafo por su peso.

Un árbol de expansión mínimo de un grafo ponderado conectado es un subgrafo conectado, sin ciclos, para el cual la suma de los pesos de todas las aristas del subgrafo es mínima. Para un grafo desconectado, un bosque de expansión mínimo se compone de un árbol de expansión mínimo para cada componente conectado .

Este algoritmo fue publicado por primera vez por Joseph Kruskal en 1956, ^[3] y fue redescubierto poco después por Loberman y Weinberger (1957). ^[4] Otros algoritmos para este problema incluyen el algoritmo de Prim , el algoritmo de Borůvka y el algoritmo de eliminación inversa .

Algoritmo

El algoritmo realiza los siguientes pasos:

Cree un bosque (un conjunto de árboles) que inicialmente consta de un árbol de vértice único separado para cada vértice en el gráfico de entrada.
Ordenar los bordes del gráfico por peso.
Recorrer los bordes del gráfico en orden ascendente según su peso. Para cada borde:
- Pruebe si agregar el borde al bosque actual crearía un ciclo.
- En caso contrario, añade el borde al bosque, combinando dos árboles en un solo árbol.

Al finalizar el algoritmo, el bosque forma un bosque de expansión mínima del grafo. Si el grafo es conexo, el bosque tiene un solo componente y forma un árbol de expansión mínima.

Pseudocódigo

El código siguiente se implementa con una estructura de datos de conjunto disjunto . Representa el bosque F como un conjunto de aristas no dirigidas y utiliza la estructura de datos de conjunto disjunto para determinar de manera eficiente si dos vértices son parte del mismo árbol.

El algoritmo Kruskal( G ) es
    F:= ∅
    para cada v en GV hacer
        HACER-CONJUNTO(v)
    para cada {u, v} en GE ordenado por peso({u, v}), aumentando do 
        si FIND-SET(u) ≠ FIND-SET(v) entonces
            F := F ∪ { {u, v} }
            UNIÓN(ENCONTRAR-CONJUNTO(u), ENCONTRAR-CONJUNTO(v))
    devolver F

Complejidad

Para un grafo con $E$ aristas y $V$ vértices, se puede demostrar que el algoritmo de Kruskal se ejecuta en un tiempo $O (E log E)$ , con estructuras de datos simples. Aquí, $O$ expresa el tiempo en notación O mayúscula , y $log$ es un logaritmo en cualquier base (ya que dentro de la notación $O$ los logaritmos en todas las bases son equivalentes, porque son los mismos hasta un factor constante). Este límite de tiempo a menudo se escribe como $O (E log V)$ , que es equivalente para grafos sin vértices aislados, porque para estos grafos $V /2 \leq E < V 2$ y los logaritmos de $V$ y $E$ están nuevamente dentro de un factor constante entre sí.

Para lograr este límite, primero ordene los bordes por peso usando un ordenamiento por comparación en tiempo $O (E log E)$ . Una vez ordenados, es posible recorrer los bordes en orden ordenado en tiempo constante por borde. A continuación, use una estructura de datos de conjunto disjunto , con un conjunto de vértices para cada componente, para realizar un seguimiento de qué vértices están en qué componentes. La creación de esta estructura, con un conjunto separado para cada vértice, requiere $V$ operaciones y tiempo $O (V)$ . La iteración final a través de todos los bordes realiza dos operaciones de búsqueda y posiblemente una operación de unión por borde. Estas operaciones toman tiempo amortizado $O (α (V))$ tiempo por operación, dando un tiempo total en el peor de los casos $O (E α (V))$ para este bucle, donde $α es la$ función de Ackermann inversa de crecimiento extremadamente lento . Esta parte del límite de tiempo es mucho menor que el tiempo para el paso de ordenamiento, por lo que el tiempo total para el algoritmo se puede simplificar al tiempo para el paso de ordenamiento.

En los casos en que los bordes ya están ordenados, o donde tienen un peso entero lo suficientemente pequeño como para permitir que algoritmos de ordenamiento de enteros , como el ordenamiento por conteo o el ordenamiento por base, los ordenen en tiempo lineal, las operaciones de conjuntos disjuntos son la parte restante más lenta del algoritmo y el tiempo total es $O (E α(V))$ .

Ejemplo

Prueba de corrección

La prueba consta de dos partes. En primer lugar, 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 grafo conexo y ponderado y sea el subgrafo de producido por el algoritmo. no puede tener un ciclo, ya que por definición no se agrega una arista si da como resultado un ciclo. no puede desconectarse, ya que la primera arista encontrada que une dos componentes de habría sido agregada por el algoritmo. Por lo tanto, es un árbol de expansión de . ${\estilo de visualización G}$ ${\estilo de visualización Y}$ ${\estilo de visualización G}$ ${\estilo de visualización Y}$ ${\estilo de visualización Y}$ ${\estilo de visualización Y}$ ${\estilo de visualización Y}$ ${\estilo de visualización G}$

Minimalismo

Demostramos que la siguiente proposición P es verdadera por inducción : si F es el conjunto de aristas elegidas en cualquier etapa del algoritmo, entonces existe un árbol de expansión mínimo que contiene F y ninguna de las aristas rechazadas por el algoritmo.

Claramente P es verdadero 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.
Ahora supongamos que P es verdadero para algún conjunto de aristas no finales F y sea T un árbol de expansión mínimo que contiene F.
- Si el siguiente borde elegido e también está en T , entonces P es verdadero para F + e .
- De lo contrario, si e no está en T entonces T + e tiene un ciclo C . El ciclo C contiene aristas que no pertenecen a F + e , ya que e no forma un ciclo cuando se suma a F pero sí en T . Sea f una arista que está en C pero no en F + e . Nótese que f también pertenece a T , ya que f pertenece a T + e pero no a F + e . Por P , f no ha sido considerada por el algoritmo. f debe tener por lo tanto un peso al menos tan grande como e . Entonces T − f + e es un árbol, y tiene el mismo peso o menos que T . Sin embargo, dado que T es un árbol de expansión mínima, entonces T − f + e tiene el mismo peso que T , de lo contrario obtenemos una contradicción y T no sería un árbol de expansión mínima. Entonces T − f + e es un árbol de expansión mínima que contiene F + e y nuevamente P se cumple.
Por lo tanto, por el principio de inducción, P se cumple cuando F se ha convertido en un árbol de expansión, lo que sólo es posible si F es en sí mismo 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 ordenació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. ^[5] Como la ordenación paralela es posible en el tiempo en los procesadores, ^[6] 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 . $O(n)$ $O(\log n)$

^{Osipov et al. [7]} describieron una variante del algoritmo de Kruskal, denominada Filter-Kruskal, que es más adecuada para la paralelización. La idea básica detrás de Filter-Kruskal es dividir las aristas de una manera similar a la ordenación rápida y filtrar las aristas que conectan vértices del mismo árbol para reducir el costo de la ordenación. El siguiente pseudocódigo demuestra esto.

La función filter_kruskal(G) es 
    si |GE| < kruskal_threshold:
         devuelve kruskal(G)
    pivote = elegir_aleatorio(GE)
    E _≤ , E _> = partición(GE, pivote)
    A = filtro_kruskal(E _≤ )
    E _> = filtro(E _> )
    A = A ∪ filter_kruskal(E _> )
     devuelve A

función partición(E, pivote) es 
    E _≤ = ∅, E _> = ∅
     foreach (u, v) en E hacer 
        si peso(u, v) ≤ pivote entonces 
            E _≤ = E _≤ ∪ {(u, v)}
         de lo contrario 
            E _> = E _> ∪ {(u, v)}
     devuelve E _≤ , E _>

función filter(E) es 
    E _f = ∅
     foreach (u, v) en E hacer 
        si find_set(u) ≠ find_set(v) entonces 
            E _f = E _f ∪ {(u, v)}
     devolver E _f

El filtro Kruskal se presta mejor a la paralelización, ya que la clasificación, el filtrado y la partición se pueden realizar fácilmente en paralelo distribuyendo los bordes entre los procesadores. ^[7]

Por último, se han explorado otras variantes de una implementación paralela del algoritmo de Kruskal. Algunos ejemplos incluyen un esquema que utiliza subprocesos auxiliares para eliminar aristas que definitivamente no son parte del MST en segundo plano, ^[8] y una variante que ejecuta el algoritmo secuencial en p subgrafos y luego fusiona esos subgrafos hasta que solo quede uno, el MST final. ^[9]

Véase también

Referencias

^ Kleinberg, Jon (2006). Diseño de algoritmos. Eva Tardos. Boston: Pearson/Addison-Wesley. págs. 142-151. ISBN 0-321-29535-8.OCLC 57422612 .
^ Cormen, Thomas; Charles E Leiserson, Ronald L Rivest, Clifford Stein (2009). Introducción a los algoritmos (Tercera ed.). Prensa del MIT. págs.631. ISBN 978-0262258104.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
^ Kruskal, JB (1956). "Sobre el subárbol de expansión más corto de un grafo y el problema del viajante de comercio". Actas de la American Mathematical Society . 7 (1): 48–50. doi : 10.1090/S0002-9939-1956-0078686-7 . JSTOR 2033241.
^ Loberman, H.; Weinberger, A. (octubre de 1957). "Procedimientos formales para conectar terminales con una longitud de cable total mínima". Revista de la ACM . 4 (4): 428–437. doi : 10.1145/320893.320896 . S2CID 7320964.
^ Quinn, Michael J.; Deo, Narsingh (1984). "Algoritmos de gráficos paralelos". Encuestas de Computación ACM . 16 (3): 319–348. doi : 10.1145/2514.2515 . S2CID 6833839.
^ Grama, Ananth; Gupta, Anshul; Karypis, George; Kumar, VIPIN (2003). Introducción a la Computación Paralela . Addison-Wesley. págs. 412–413. ISBN 978-0201648652.
^ ab Osipov, Vitaly; Sanders, Peter; Singler, Johannes (2009). "El algoritmo de árbol de expansión mínimo de filtro-kruskal". Actas del undécimo taller sobre ingeniería de algoritmos y experimentos (ALENEX). Sociedad de Matemáticas Industriales y Aplicadas : 52–61. doi : 10.1137/1.9781611972894.5 . ISBN 978-0-89871-930-7.
^ Katsigiannis, Anastasios; Anastopoulos, Nikos; Konstantinos, Nikas; Koziris, Nectarios (2012). "Un enfoque para paralelizar el algoritmo de Kruskal utilizando subprocesos auxiliares". 2012 IEEE 26.º Simposio internacional de procesamiento distribuido y paralelo, talleres y foro de doctorado (PDF) . págs. 1601-1610. doi :10.1109/IPDPSW.2012.201. ISBN 978-1-4673-0974-5.S2CID14430930 .
^ Lončar, Vladimir; Škrbić, Srdjan; Balaž, Antun (2014). "Paralelización de algoritmos de árbol de expansión mínimo utilizando arquitecturas de memoria distribuida". Transactions on Engineering Technologies . págs. 543–554. doi :10.1007/978-94-017-8832-8_39. ISBN 978-94-017-8831-1.

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.