Swappa : Uni / Strutture dati per insiemi disgiunti
Creative Commons License

Torna alla pagina di Algoritmi e strutture dati


Questa pagina è stata aggiornata GRAZIE agli appunti che AVETE INVIATO nel periodo di chiusura della sezione UniCrema!! È SERVITA A QUALCOSA, NO?! ;)

 :: Strutture dati per insiemi disgiunti ::

Gli insiemi disgiunti sono insiemi i cui elementi sono tutti distinti.
Gli insiemi disgiunti organizzati in collezioni vengono mantenuti in strutture dati. Ogni insieme viene identificato da un elemento particolare detto rappresentante. Ogni elemento degli insiemi viene rappresentato da un oggetto.
Dato un oggetto x, posso eseguire le seguenti operazioni:

Una semplice rappresentazione di questi insiemi è data dalle liste concatenate.
Il primo oggetto di ogni lista viene utilizzato come rappresentante.
Ogni oggetto nella lista contiene:

MAKE–SET: crea una nuova lista concatenata, con un unico oggetto x. O(1).
FIND–SET: restituisce il puntatore da x al rappresentante. O(1).
UNION: eseguita appendendo la lista di x alla fine di quella di y e il rappresentante del nuovo insieme è l'elemento che era il rappresentante dell'insieme di y. Purtroppo deve essere aggiornato il puntatore al rappresentante per ogni nodo della lista più lunga. teta(n2) dove n2 è la lunghezza della seconda lista.

Supponendo che ogni rappresentante contenga anche la lunghezza (lung) della lista e che si appenda sempre la lista più corta a quella più lunga, si parla di EURISTICA PER L'UNIONE PESATA.

Un altro tipo di rappresentazione ma più efficiente e veloce è data dagli alberi radicati. Ogni nodo contiene un elemento ed ogni albero rappresenta un insieme.
In una foresta di insiemi disgiunti ogni elemento ha un puntatore solo al padre. La radice contiene il rappresentante.

MAKE–SET: crea un albero con un solo nodo;
FIND–SET: eseguita controllando i puntatori al padre fino a che non viene trovata la radice dell'albero.
UNION: la radice di un albero punta alla radice di un altro albero.

Euristica dell'unione per rango: simile a quella per l'unione pesata vista per le liste. La radice dell'albero più basso deve puntare a quella dell'albero più alto.
Per ogni nodo si tiene un rango che è un limite superiore all'altezza dell'albero.
In sostanza, la radice con rango più piccolo punta alla radice con rango maggiore nel corso dell'UNION. Se eseguita individualmente: O(m log n) dove m sono il numero di operazioni e n il numero di operazioni MAKE–SET.

Euristica della compressione dei cammini: usata per le FIND–SET per far si che ogni nodo sul cammino di accesso punti direttamente alla radice.
Se eseguita individualmente:

teta (n + f log n) , se f < n;
teta (f log (1 + f/n) n) , se f >= n.

dove m sono il numero di operazioni, n quelle MAKE–SET e f quelle FIND–SET.


Torna alla pagina di Algoritmi e strutture dati

(Printable View of http://www.swappa.it/wiki/Uni/A-SDInsiemiDisgiunti)