LabASD - Strutture Merge-Find

Moreno Marzolla

Ultimo aggiornamento: 2023-04-26

In questo esercizio implementiamo una struttura dati per insiemi disgiunti, detta struttura Merge-Find o Union-Find o Up-Tree. L’interfaccia è descritta nel file mfset.h e viene implementata in nfset.c.

Una struttura merge-find di dimensione \(n\) è inizialmente costituita da \(n\) insiemi disgiunti \(\{0\}, \{1\}, \ldots, \{n-1\}\). In questo esercizio implementiamo la versione QuickUnion, che supporta in modo efficiente l’operazione di unione. Nelle strutture QuickUnion, ogni insieme è rappresentato da un albero i cui nodi sono gli elementi dell’insieme. La foresta di alberi è realizzata con un vettore di padri p[]. Dato un elemento \(x \in \{0, \ldots, n-1\}\), p[x] denota il padre di \(x\). Nel caso in cui \(x\) sia la radice di un albero, e quindi non abbia padre, si pone p[x] = x.

Figura 1: Esempio di foresta merge-find che rappresenta gli insiemi \{0, 2, 3, 5, 7, 9, 10\}, \{1, 4, 8\}, \{6\}
Figura 1: Esempio di foresta merge-find che rappresenta gli insiemi \(\{0, 2, 3, 5, 7, 9, 10\}\), \(\{1, 4, 8\}\), \(\{6\}\)

Ad esemipo, nella Figura 1 mostriamo un esempio di struttura merge-find con \(n=11\) elementi appartenenti all’insieme \(\{0, \ldots, 10\}\) organizzati in tre insiemi disgiunti. I tre alberi merge-find sono codificati dall’array di padri p[] mostrato. Vediamo ad esempio che \(p[0] = 7\) in quanto il padre del nodo 0 nella foresta merge-find è il nodo 7, mentre \(p[7] = 7\) perché il nodo 7 è la radice dell’albero di cui fa parte.

L’operazione di unione è realizzata dalla funzione mfset_merge(s, x, y) che, data una struttura merge-find s e due interi \(x, y\) che rappresentano due valori dell’insieme \(\{0, \ldots, n-1\}\), modifica s in modo che gli insiemi contenenti \(x\) e \(y\) vengano fusi. Per fare ciò, si identificano le radici \(x_R\) e \(y_R\) degli insiemi contenenti \(x\) e \(y\), rispettivamente, e si rende una delle due (ad esempio \(y_R\)) figlia dell’altra (ad esempio, \(x_R\)).

Figura 2: Struttura dati risultante dopo l’operzione merge(s, 5, 1)
Figura 2: Struttura dati risultante dopo l’operzione merge(s, 5, 1)

In Figura 2 mostriamo come cambia la struttura dati dopo l’operazione merge(s, 5, 1). La radice dell’albero contenente \(x=5\) è \(x_R = 7\); la radice dell’albero contenente \(y = 1\) è \(y_R = 4\). Si rende quindi il nodo \(4\) figlio del nodo \(7\) ponendo \(p[4] \leftarrow 7\), ottenendo l’albero mostrato.

Il programma mfset-main.c contiene una funzione main() che legge da un file, il cui nome viene passato sulla riga di comando, una sequenza di comandi che manipolano una struttura merge-find. I comandi riconosciuti sono elencati nella Tabella 1 (le lettere in corsivo indicano valori numerici).

Tabella 1: Comandi nel file di input
Comando Significato
n Crea una struttura MF con n nodi; questo comando è sempre il primo e compare una sola volta
m x y Fonde gli insiemi contenenti x e y
q x y Determina se x e y appartengono allo stesso insieme

dove \(n\) è un intero positivo, e \(x, y\) sono interi compresi tra 0 e \(n-1\) (inclusi).

Per compilare il programma dalla riga di comando:

    gcc -std=c90 -Wall -Wpedantic mfset.c mfset-main.c -o mfset

Per eseguire in ambiente Linux/MacOSX:

    ./mfset-main mfset.in

Per eseguire in ambiente Windows:

    .\mfset-main mfset.in

Per approfondire

Chi lo desidera può implementare qualche euristica tra quelle viste a lezione. L’euristica di compressione dei cammini consente di limitare l’altezza degli alberi, e si realizza con una modifica della funzione mfset_find() vista a lezione. L’idea è che, ogni volta in cui si effettua una operazsione find(x) per trovare la radice dell’albero contenente \(x\), tutti i nodi che si incontrano nel cammino da \(x\) alla radice vengono resi figli della radice.

Un’altra possibilità per migliorare le prestazioni di una struttura merge-find è l’euristica union by rank, che consiste nel tenere traccia dell’altezza di ciascun albero, in modo che mfset_merge() renda la radice dell’albero più basso figlia di quella dell’albero più alto. L’altezza degli alberi può essere mantenuta nell’array ausiliario h[] definito nella struttura MFSet:

typedef struct {
    int n;
    int *p;
    int *h;
} MFSet;

h[] ha lunghezza \(n\), e h[x] deve rappresentare l’altezza dell’albero che ha \(x\) come radice; se \(x\) non è la radice di un albero, il valore h[x] non viene utilizzato ed è quindi ininfluente.

Inizialmente tutte le altezze valgono zero (un albero composto da un singolo nodo ha altezza zero). Quando si effettua l’unione di due alberi con radice \(x_R, y_R\) rispettivamente, si possono verificare i casi seguenti:

L’euristica union by rank è più laboriosa da implementare rispetto alla compressione dei cammini, ed è anche un po’ meno efficiente, ma costituisce comunque un interessante esercizio per chi vuole provare.

File