Algoritmo de Kruskal

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Algoritmo de bosque que ambiciosamente añade bordes

El algoritmo de Kruskal encuentra un bosque de expansión mínima de un gráfico ponderado por borde no dirigido. Si el gráfico es conexo, 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 forman un árbol que incluye cada vértice, donde la suma de los pesos de todos los bordes del árbol se minimiza. 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 peso más bajo 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, pp. 48–50 en 1956, y fue escrito por Joseph Kruskal. Fue redescubierto por Loberman & Weinberger (1957).

Otros algoritmos para este problema incluyen el algoritmo de Prim, el algoritmo de eliminación inversa 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 ordenados S que contiene todos los bordes del gráfico
mientras S es indeseable F todavía no está azotando
- quitar un borde con peso mínimo S
- si el borde removido conecta dos árboles diferentes, a continuación, añadirlo al bosque F, combinando dos árboles en un solo árbol

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

Pseudocódigo

Demo para el algoritmo de Kruskal en un gráfico completo con pesos basados en la distancia de Euclidean.

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

algoritmo KruskalG) esF:= ∅
 para cada uno v doMAKE-SET(v)
 para cada uno (u, v) dentro G.E ordenado por peso(u, v), aumentando do si FIND-SET(u) ل FIND-SET(v) entoncesF:= F ∪ {(u, v)} {(v, u)}
UNION(FIND-SET(u), FIND-SET(v))
 retorno F

Complejidad

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

E es en la mayoría $V^{2}$ y ${displaystyle log V^{2}=2log Vin O(log V)}$ .
Cada vértice aislado es un componente separado del bosque mínimo de azotes. Si ignoramos vertices aislados obtenemos V ≤ 2E, así que log V es ${displaystyle O(log E)}$ .

Podemos lograr este límite de la siguiente manera: primero ordene los bordes por peso usando una ordenación de comparación en tiempo O(E log E); esto permite que el paso "elimine un borde con el peso mínimo de S" operar en tiempo constante. A continuación, usamos una estructura de datos de conjunto disjunto para realizar un seguimiento de qué vértices están en qué componentes. Colocamos cada vértice en su propio conjunto disjunto, que requiere 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 'buscar' operaciones y posiblemente un sindicato. Incluso una estructura de datos de conjuntos disjuntos simple, como bosques de conjuntos disjuntos con unión por rango, puede realizar operaciones O(E) en O(E log V) de tiempo. Por tanto, el tiempo total es O(E log E) = O(E registro V).

Siempre que los bordes ya estén ordenados o se puedan ordenar en tiempo lineal (por ejemplo, con clasificación por conteo o clasificación por base), el algoritmo puede usar una estructura de datos de conjuntos disjuntos más sofisticada para ejecutarse en O(E α(V)) tiempo, donde α es el inverso de crecimiento extremadamente lento de la función de Ackermann de valor único.

Ejemplo

Imagen	Descripción
	AD y CE son los bordes más cortos, con la longitud 5, y AD ha sido elegido arbitrariamente, por lo que se destaca.
	CE es ahora el borde más corto que no forma un ciclo, con la longitud 5, por lo que se destaca como el segundo borde.
	El próximo borde, DF con la longitud 6, se destaca utilizando mucho el mismo método.
	Los bordes más cortos son AB y BE, ambos con longitud 7. AB es elegido arbitrariamente, y se destaca. El borde BD se ha destacado en rojo, porque ya existe un camino (en verde) entre B y D, por lo que formaría un ciclo (ABDSi fuera elegido.
	El proceso continúa destacando el borde más corto, BE con longitud 7. Muchos más bordes se destacan en rojo en esta etapa: BC porque formaría el bucle BCE, DE porque formaría el bucle DEBA, y FE porque formaría FEBAD.
	Finalmente, el proceso termina con el borde EG de la longitud 9, y el árbol de azotes mínimo se encuentra.

Prueba de corrección

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

Árbol de expansión

Vamos $G$ ser un gráfico conectado, ponderado y dejar $Y$ ser el subgrafo de $G$ producido por el algoritmo. $Y$ no puede tener un ciclo, como por definición no se añade un borde si resulta en un ciclo. $Y$ no se puede desconectar, ya que el primer borde encontrado que une dos componentes de $Y$ habría sido añadido por el algoritmo. Así, $Y$ es un árbol de azotes $G$ .

Minimalidad

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

Claramente P es verdad al principio, cuando F está vacío: cualquier árbol de azotes mínimo hará, y existe uno porque un gráfico conectado ponderado siempre tiene un árbol de azotes mínimo.
Ahora asume P es cierto para algún filo no final F y dejar T ser un árbol mínimo que contiene F.
- Si el próximo borde elegido e también está T, entonces P es verdad F + e.
- Si no, e no está T entonces T + e tiene un ciclo C. Este ciclo contiene bordes que no pertenecen a F, desde e no forma un ciclo cuando se añade a F pero lo hace T. Vamos f ser un borde que está en C pero no en F + e. Note que f también pertenece a T, y por P, no ha sido considerado por el algoritmo. f por lo tanto 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. Así que... T − f + e es un árbol de lazo mínimo que contiene F + e y otra vez P sostiene.
Por lo tanto, por el principio de inducción, P sostiene cuando F se ha convertido en un árbol de azotes, que sólo es posible F es un árbol de azotes mínimo en sí mismo.

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 clasificación paralela es posible a tiempo $O(n)$ on $O(log n)$ procesadores, el tiempo de funcionamiento del algoritmo de Kruskal se puede reducir a O()E α(V)), donde α de nuevo es el inverso de la función Ackermann de valor único.

Osipov et al. han descrito una variante del algoritmo de Kruskal, denominada Filter-Kruskal. 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 la clasificación. El siguiente pseudocódigo demuestra esto.

función filter_kruskal(G) es si TENG.E sometida Identificado kruskal_threshold:
 retorno kruskal(G)
pivote = choose_random(G.E)
  ${displaystyle E_{leq }}$ ,  $}}" xmlns="http://www.w3.org/1998/Math/MathML"> E ■ {displaystyle E_{}} }}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8177e4a33a0ba0954aa9c464556d44475c27b841" style="vertical-align: -0.671ex; width:3.226ex; height:2.509ex;"/>$  = partición (G.E, pivote)
A = filter_kruskal( ${displaystyle E_{leq }}$ )
  $}}" xmlns="http://www.w3.org/1998/Math/MathML"> E ■ {displaystyle E_{}} }}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8177e4a33a0ba0954aa9c464556d44475c27b841" style="vertical-align: -0.671ex; width:3.226ex; height:2.509ex;"/>$  = filtro $}}" xmlns="http://www.w3.org/1998/Math/MathML"> E ■ {displaystyle E_{}} }}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8177e4a33a0ba0954aa9c464556d44475c27b841" style="vertical-align: -0.671ex; width:3.226ex; height:2.509ex;"/>$ )
A = A ∪ filter_kruskal $}}" xmlns="http://www.w3.org/1998/Math/MathML"> E ■ {displaystyle E_{}} }}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8177e4a33a0ba0954aa9c464556d44475c27b841" style="vertical-align: -0.671ex; width:3.226ex; height:2.509ex;"/>$ )
 retorno A

función partición (E, pivote) es  ${displaystyle E_{leq }}$  = ∅,  $}}" xmlns="http://www.w3.org/1998/Math/MathML"> E ■ {displaystyle E_{}} }}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8177e4a33a0ba0954aa9c464556d44475c27b841" style="vertical-align: -0.671ex; width:3.226ex; height:2.509ex;"/>$  = ∅
 en adelante (u, v) en E do si peso(u, v) entonces  ${displaystyle E_{leq }}$  =  ${displaystyle E_{leq }}$  u {(u, v)}
 más  $}}" xmlns="http://www.w3.org/1998/Math/MathML"> E ■ {displaystyle E_{}} }}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8177e4a33a0ba0954aa9c464556d44475c27b841" style="vertical-align: -0.671ex; width:3.226ex; height:2.509ex;"/>$  =  $}}" xmlns="http://www.w3.org/1998/Math/MathML"> E ■ {displaystyle E_{}} }}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8177e4a33a0ba0954aa9c464556d44475c27b841" style="vertical-align: -0.671ex; width:3.226ex; height:2.509ex;"/>$  u {(u, v)}
 retorno  ${displaystyle E_{leq }}$ ,  $}}" xmlns="http://www.w3.org/1998/Math/MathML"> E ■ {displaystyle E_{}} }}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8177e4a33a0ba0954aa9c464556d44475c27b841" style="vertical-align: -0.671ex; width:3.226ex; height:2.509ex;"/>$ función filter(E) es  ${displaystyle E_{text{filtered}}}$  = ∅
 en adelante (u, v) en E do si find_set(u) ل find_set(v) entonces  ${displaystyle E_{text{filtered}}}$  =  ${displaystyle E_{text{filtered}}}$  u {(u, v)}
 retorno  ${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.

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

Contenido relacionado

Más resultados...