Torna alla pagina di Algoritmi e strutture dati

 :: 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:

• MAKE–SET(x): viene creato un nuovo insieme con un solo membro che è x (quindi x è anche il rappresentante). X non deve essere presente in nessun altro insieme dato che gli elementi devono essere disgiunti.
• UNION(x,y): unisce due insiemi contenenti x e y in un nuovo insieme. Gli insiemi devono essere disgiunti.
• FIND–SET(x): restituisce il puntatore al rappresentate dell'insieme (unico) che contiene x.

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:

• info: un elemento dell'insieme;
• rappr: puntatore all'indietro al rappresentante;
• succ: un puntatore all'oggetto contenuto nel successivo elemento dell'insieme.

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:

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

Torna alla pagina di Algoritmi e strutture dati