algorithm
Algoritmo di Kruskal

Osservazioni

Implementazione semplice e più dettagliata

Per gestire in modo efficiente il rilevamento del ciclo, consideriamo ogni nodo come parte di un albero. Quando aggiungiamo un bordo, controlliamo se i suoi due nodi componenti fanno parte di alberi distinti. Inizialmente, ciascun nodo costituisce un albero a 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

Semplice implementazione basata su un insieme disgiunto

La suddetta metodologia forestale è in realtà una struttura di dati disgiunti, che prevede tre operazioni principali:

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)

Questa ingenua implementazione porta a O(n log n) tempo per la gestione della struttura dati disgiunti, che porta a O(m*n log n) tempo per l'intero algoritmo di Kruskal.

Implementazione ottimale, basata su un insieme disgiunto

Possiamo fare due cose per migliorare i subalgoritmi set disgiunti semplici e sub-ottimali:

1. findSet compressione percorso : findSet non ha bisogno di gestire mai un albero con altezza superiore a 2 . Se finisce iterando un albero del genere, può collegare i nodi inferiori direttamente alla radice, ottimizzando gli attraversamenti futuri;

   subalgo findSet(v: a node):
       if v.parent != v
           v.parent = findSet(v.parent)
       return v.parent
   

2. Euristica di unione basata sull'altezza: per ogni nodo, memorizza l'altezza del relativo sottoalbero. Quando si uniscono, rendere l'albero più alto il genitore di quello più piccolo, quindi non aumentare l'altezza di nessuno.

   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
   

Questo porta al tempo O(alpha(n)) per ogni operazione, dove alpha è l'inverso della funzione Ackermann a crescita rapida, quindi è una crescita molto lenta e può essere considerata O(1) per scopi pratici.

Questo rende l'intero algoritmo di Kruskal O(m log m + m) = O(m log m) , a causa dell'ordinamento iniziale.

Nota

La compressione del percorso può ridurre l'altezza dell'albero, quindi confrontare le altezze degli alberi durante l'operazione di unione potrebbe non essere un compito banale. Quindi per evitare la complessità di memorizzare e calcolare l'altezza degli alberi il genitore risultante può essere scelto casualmente:

    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

In pratica questo algoritmo randomizzato insieme alla compressione del percorso per findSet operazione findSet si tradurrà in prestazioni comparabili, ma molto più semplici da implementare.

Implementazione semplice e di alto livello

Ordinare i bordi per valore e aggiungerli al MST in ordine ordinato, se non 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