Mfset

L' MFSet (Merge-Find Set) è una struttura dati derivante dal concetto di Insieme delle parti, per cui dato un insieme finito di elementi a volte risulta utile partizionarli in insiemi disgiunti. L'algoritmo di Merge-Find è quindi utile per le due operazioni possibili su questa struttura dati:

• Ricerca: determina in quale insieme si trova un particolare elemento, o se due elementi appartengono allo stesso insieme
• Unione: combina o fonde due insiemi in un unico insieme

L'altra operazione su MFSet è CreaMFSet tramite la quale è possibile dato un insieme crearne l'insieme delle parti di ciascun elemento. Con l'utilizzo di questi tre operatori è possibile risolvere molti problemi pratici.

Operatori

Sintassi

• CREAMFSET (INSIEME) $\rightarrow$ MFSet
• TROVA (ELEMENTO, MFSET) $\rightarrow$ componente
• FONDI (ELEMENTO, ELEMENTO, MFSET) $\rightarrow$ MFSet

Semantica

• CREAMFSET($\mathit{A}$)=$\mathit{S}$

$\mathit{S}$ è quindi una famiglia di $\mathit{n}$ = |$\mathit{A}$| componenti $\mathit{C_1}$,...,$\mathit{C_n}$ ciascuno dei quali contiene un solo elemento di $\mathit{A}$ tale che $\bigcup_i^{n} \mathit{C_i}$= $\mathit{A}$.

• TROVA($\mathit{x},\mathit{S}) = \mathit{C}$

se $\mathit{x}$ appartiene ad una componente di $\mathit{S}$ allora $\mathit{C}$ è l'identificatore della componente cui $\mathit{x}$ appartiene.

• FONDI($\mathit{x}, \mathit{y}, \mathit{S})=S'$

se TROVA($\mathit{x}, \mathit{S})$ è diverso da $TROVA(\mathit{y, S})$ quindi $\mathit{x}$ ed $\mathit{y}$ appartengono a componenti distinte di $\mathit{S}$ allora $\mathit{S'}$ è formato da tutte le componenti di $\mathit{S}$ che non contengono $\mathit{x}$ o $\mathit{y}$, e da una nuova componente data dall'unione delle due componenti contenenti $\mathit{x}$ ed $\mathit{y}$.