algorithm
Algoritmo di Kruskal

.NET Framework C Language C# Language C++ Java Language JavaScript MATLAB Language PHP Python Language Ruby Language
Ricerca…


Osservazioni

L'Algoritmo di Kruskal è un algoritmo avido usato per trovare lo Spanning Tree (MST) minimo di un grafico. Un albero di copertura minimo è un albero che collega tutti i vertici del grafico e ha il peso totale minimo del bordo.

L'algoritmo di Kruskal lo fa prelevando ripetutamente i bordi con il peso minimo (che non sono già nel MST) e li aggiunge al risultato finale se i due vertici collegati da quel bordo non sono ancora connessi nel MST, altrimenti salta quel bordo. Unione - Trova la struttura dei dati può essere usato per verificare se due vertici sono già collegati nel MST o no. Alcune proprietà di MST sono le seguenti:

  1. Un MST di un grafico con n vertici avrà esattamente bordi n-1 .
  2. Esiste un percorso univoco da ciascun vertice a ogni altro vertice.

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


Modified text is an extract of the original Stack Overflow Documentation
Autorizzato sotto CC BY-SA 3.0
Non affiliato con Stack Overflow