algorithm
El algoritmo de Kruskal

.NET Framework C Language C# Language C++ Java Language JavaScript MATLAB Language PHP Python Language Ruby Language
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:

  1. Un MST de una gráfica con n vértices tendrá exactamente n-1 aristas.
  2. 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:

  1. Heurística de compresión de ruta : findSet no necesita manejar un árbol con una altura mayor a 2 . 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.parent

  2. Heurí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


Modified text is an extract of the original Stack Overflow Documentation
Licenciado bajo CC BY-SA 3.0
No afiliado a Stack Overflow