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) ${\displaystyle \rightarrow }$ MFSet
• TROVA (ELEMENTO, MFSET) ${\displaystyle \rightarrow }$ componente
• FONDI (ELEMENTO, ELEMENTO, MFSET) ${\displaystyle \rightarrow }$ MFSet

Semantica

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

${\displaystyle {\mathit {S}}}$ è quindi una famiglia di ${\displaystyle {\mathit {n}}}$ = |${\displaystyle {\mathit {A}}}$| componenti ${\displaystyle {\mathit {C_{1}}}}$,...,${\displaystyle {\mathit {C_{n}}}}$ ciascuno dei quali contiene un solo elemento di ${\displaystyle {\mathit {A}}}$ tale che ${\displaystyle \bigcup _{i}^{n}{\mathit {C_{i}}}}$= ${\displaystyle {\mathit {A}}}$.

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

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

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

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