LabASD - Strutture Merge-Find

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-04-23

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\}\); ogni insieme è rappresentato da un albero. 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\), se esiste. Nel caso in cui \(x\) sia la radice di un albero si può porre p[x] = -1.

Il programma mfset-main.c contiene una funzione main() che legge da standard input (oppure da un file il cui nome viene passato su riga di comando) una sequenza di comandi che manipolano una struttura merge-find. I comandi riconosciuti sono i seguenti (le lettere in corsivo indicano valori numerici):

Comando Significato
n Crea una struttura MF con n nodi; questo comando è sempre il primo e compare una sola volta
m i j Fonde gli insiemi contenenti i e j
q i j Determina se i e j appartengono allo stesso insieme

dove \(n\) è un intero positivo, e \(i, j\) 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:

    ./mfset-main < mfset.in

oppure:

    ./mfset-main mfset.in

Per approfondire

Chi lo desidera può implementare qualche euristica tra quelle viste a lezione. Ad esempio, l'euristica union by rank consiste nel tenere traccia dell'altezza di ciascun albero, e realizzare l'operazione mfset_merge() facendo in modo che la radice dell'albero più basso diventi 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 radicato in \(x\), per ogni radice \(x\).

File