Mfset

L'MFSet (Merge-Find Set), altrimenti conosciuto come struttura dati union-find, è una struttura dati derivante dal concetto di partizione, 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 è Crea, tramite la quale è possibile dato un insieme crearne la partizione formata solo da singoletti. Con l'utilizzo di questi tre operatori è possibile risolvere molti problemi pratici.

Operazioni

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}}$.