algorithm
El algoritmo de Kruskal
Buscar..
Observaciones
El algoritmo de Kruskal es un algoritmo codicioso que se utiliza para encontrar el árbol de expansión mínimo (MST) de un gráfico. Un árbol de expansión mínimo es un árbol que conecta todos los vértices de la gráfica y tiene el peso total mínimo del borde.
El algoritmo de Kruskal lo hace al seleccionar repetidamente bordes con un peso mínimo (que aún no están en el MST) y agregarlos al resultado final si los dos vértices conectados por ese borde aún no están conectados en el MST, de lo contrario, se salta ese borde. Unión: la estructura de datos de búsqueda se puede usar para verificar si dos vértices ya están conectados en el MST o no. Algunas propiedades de MST son las siguientes:
- Un MST de una gráfica con
nvértices tendrá exactamenten-1aristas. - Existe una ruta única de cada vértice a cada otro vértice.
Implementación simple, más detallada.
Para manejar de manera eficiente la detección de ciclos, consideramos cada nodo como parte de un árbol. Al agregar un borde, verificamos si sus dos nodos componentes forman parte de árboles distintos. Inicialmente, cada nodo forma un árbol de un nodo.
algorithm kruskalMST'(G: a graph)
sort G's edges by their value
MST = a forest of trees, initially each tree is a node in the graph
for each edge e in G:
if the root of the tree that e.first belongs to is not the same
as the root of the tree that e.second belongs to:
connect one of the roots to the other, thus merging two trees
return MST, which now a single-tree forest
Implementación simple, basada en conjuntos disjuntos
La metodología forestal anterior es en realidad una estructura de datos de conjuntos disjuntos, que involucra tres operaciones principales:
subalgo makeSet(v: a node):
v.parent = v <- make a new tree rooted at v
subalgo findSet(v: a node):
if v.parent == v:
return v
return findSet(v.parent)
subalgo unionSet(v, u: nodes):
vRoot = findSet(v)
uRoot = findSet(u)
uRoot.parent = vRoot
algorithm kruskalMST''(G: a graph):
sort G's edges by their value
for each node n in G:
makeSet(n)
for each edge e in G:
if findSet(e.first) != findSet(e.second):
unionSet(e.first, e.second)
Esta implementación ingenua lleva al tiempo O(n log n) para administrar la estructura de datos del conjunto disjunto, lo que lleva al tiempo O(m*n log n) para todo el algoritmo de Kruskal.
Implementación óptima, basada en conjuntos disjuntos
Podemos hacer dos cosas para mejorar los subalgoritmos de conjuntos disjuntos simples y subóptimos:
Heurística de compresión de ruta :
findSetno necesita manejar un árbol con una altura mayor a2. Si termina iterando tal árbol, puede vincular los nodos inferiores directamente a la raíz, optimizando futuros recorridos;subalgo findSet(v: a node): if v.parent != v v.parent = findSet(v.parent) return v.parentHeurística de fusión basada en altura : para cada nodo, almacene la altura de su subárbol. Al fusionar, convierta al árbol más alto en el padre del más pequeño, por lo que no aumentará la altura de nadie.
subalgo unionSet(u, v: nodes): vRoot = findSet(v) uRoot = findSet(u) if vRoot == uRoot: return if vRoot.height < uRoot.height: vRoot.parent = uRoot else if vRoot.height > uRoot.height: uRoot.parent = vRoot else: uRoot.parent = vRoot uRoot.height = uRoot.height + 1
Esto lleva al tiempo de O(alpha(n)) para cada operación, donde alpha es el inverso de la función de Ackermann de rápido crecimiento, por lo que su crecimiento es muy lento y puede considerarse O(1) por motivos prácticos.
Esto hace que todo el algoritmo de Kruskal O(m log m + m) = O(m log m) , debido a la clasificación inicial.
Nota
La compresión del camino puede reducir la altura del árbol, por lo tanto, comparar las alturas de los árboles durante la operación de unión podría no ser una tarea trivial. Por lo tanto, para evitar la complejidad de almacenar y calcular la altura de los árboles, el padre resultante se puede seleccionar al azar:
subalgo unionSet(u, v: nodes):
vRoot = findSet(v)
uRoot = findSet(u)
if vRoot == uRoot:
return
if random() % 2 == 0:
vRoot.parent = uRoot
else:
uRoot.parent = vRoot
En la práctica, este algoritmo aleatorio junto con la compresión de ruta para la operación findSet dará como resultado un rendimiento comparable, pero mucho más sencillo de implementar.
Implementación simple y de alto nivel.
Ordene los bordes por valor y agregue cada uno al MST en orden ordenado, si no crea un ciclo.
algorithm kruskalMST(G: a graph)
sort G's edges by their value
MST = an empty graph
for each edge e in G:
if adding e to MST does not create a cycle:
add e to MST
return MST
