algoritmo de Kruskal

El algoritmo de Kruskal ^[1] encuentra un bosque de expansión mínima de un gráfico ponderado por bordes no dirigido . Si el gráfico es conexo , encuentra un árbol de expansión mínimo . Es un algoritmo codicioso que en cada paso agrega al bosque el borde de menor peso que no formará un ciclo . ^[2] Los pasos clave del algoritmo son la clasificación y el uso de una estructura de datos de conjuntos separados para detectar ciclos. Su tiempo de ejecución está dominado por el tiempo para ordenar todos los bordes del gráfico por su peso.

Un árbol de expansión mínimo de un gráfico ponderado conectado es un subgrafo conectado, sin ciclos, para el cual la suma de los pesos de todos los bordes del subgrafo es mínima. Para un gráfico desconectado, un bosque de expansión mínima 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 redescubierto poco después por Loberman y Weinberger (1957). ^[4] Otros algoritmos para este problema incluyen el algoritmo de Borůvka , el algoritmo de Jarník y el algoritmo de eliminación inversa .

Algoritmo

El algoritmo realiza los siguientes pasos:

Cree un bosque (un conjunto de árboles) que inicialmente consista en un árbol de un solo vértice separado para cada vértice en el gráfico de entrada.
Ordena los bordes del gráfico por peso.
Recorra los bordes del gráfico, en orden ascendente ordenados por su peso. Para cada borde:
- Pruebe si agregar el borde al bosque actual crearía un ciclo
- Si no, agrega el borde al bosque, combinando dos árboles en un solo árbol.

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

Pseudocódigo

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

algoritmo Kruskal( G ) es F:= ∅ para cada v en GV hacer AJUSTE(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(BUSCAR-CONFIGURAR(u), ENCONTRAR-CONFIGURAR(v)) volver F

Complejidad

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

Para lograr este límite, primero ordene los bordes por peso usando una clasificación de comparación en tiempo $O (E log E)$ . Una vez ordenados, es posible recorrer los bordes en orden ordenado en un tiempo constante por borde. A continuación, utilice una estructura de datos de conjunto disjunto , con un conjunto de vértices para cada componente, para realizar un seguimiento de qué vértices se encuentran en qué componentes. Crear esta estructura, con un conjunto separado para cada vértice, requiere $V$ operaciones y $O (V)$ tiempo. 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) )$ por operación, lo que da el 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 tiempo límite es mucho menor que el tiempo del paso de clasificación, por lo que el tiempo total del algoritmo se puede simplificar al tiempo del paso de clasificación.

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

Ejemplo

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 generador construido tiene un peso mínimo.

Árbol de expansión

Sea un gráfico ponderado y conectado 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 se puede desconectar, ya que el algoritmo habría agregado el primer borde encontrado que une dos componentes . Por tanto, es un árbol de expansión de . $G$ $Y$ $G$ $Y$ $Y$ $Y$ $Y$ $G$

Minimalidad

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 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.
Ahora supongamos que P es cierto para algún conjunto de aristas no final 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 cierto 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 . Tenga en cuenta 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 considerado por el algoritmo. Por lo tanto, f debe tener un peso al menos tan grande como e . Entonces T − f + e es un árbol y tiene el mismo o menos peso que T . Sin embargo, dado que T es un árbol de expansión mínimo, 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ínimo. Entonces T − f + e es un árbol de expansión mínimo 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 generador, lo cual sólo es posible si F es un árbol generador 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. ^[5] Como la clasificació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. han descrito una variante del algoritmo de Kruskal, denominada Filter-Kruskal. ^[7] y es más adecuado para la paralelización. La idea básica detrás de Filter-Kruskal es dividir los bordes de 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.

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 _> ) devolver Ala función partición (E, pivote) es E _≤ = ∅, E _> = ∅ foreach (u, v) en E si peso (u  , v) ≤ pivote entonces E _≤ = E _≤ ∪ {(u, v)} else mi _> = mi _> ∪ {(u, v)} devolver mi _≤ , mi _>la función filtro (E) es E _f = ∅ foreach ( u, v) en E si find_set(u) ≠ find_set(v) entonces E _f = E _f ∪ {(u, v)} return E _f

Filter-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]

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

Ver 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}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
^ Kruskal, JB (1956). "Sobre el subárbol de extensión más corto de un gráfico y el problema del viajante". Actas de la Sociedad Matemática Estadounidense . 7 (1): 48–50. doi : 10.1090/S0002-9939-1956-0078686-7 . JSTOR 2033241.
^ Loberman, H.; Weinberger, A. (octubre de 1957). "Procedimientos formales para la conexión de terminales con una longitud mínima total de cable". 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 . págs. 412–413. ISBN 978-0201648652.
^ ab Osipov, Vitaly; Lijadoras, Peter; Soltero, Johannes (2009). "El algoritmo del árbol de expansión mínima filter-kruskal" (PDF) . Actas del undécimo taller sobre experimentos e ingeniería de algoritmos (ALENEX). Sociedad de Matemáticas Industriales y Aplicadas : 52–61.
^ 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. S2CID 14430930.
^ Loncar, Vladimir; Škrbić, Srdjan; Balaž, Antun (2014). "Paralelización de algoritmos de árbol de expansión mínimo utilizando arquitecturas de memoria distribuida". Transacciones sobre tecnologías de ingeniería. : 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.

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++
El código del algoritmo de Kruskal en C++ aplicado a números aleatorios
Código del algoritmo de Kruskal en Python con explicación