Mfset

Template:F 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) $\to$ MFSet
• TROVA (ELEMENTO, MFSET) $\to$ componente
• FONDI (ELEMENTO, ELEMENTO, MFSET) $\to$ MFSet

Semantica

• CREAMFSET($𝐴$)=$𝑆$

$𝑆$ è quindi una famiglia di $𝑛$ = |$𝐴$| componenti ${𝐶}_1$,...,${𝐶}_{𝑛}$ ciascuno dei quali contiene un solo elemento di $𝐴$ tale che $\bigcup _i^n{𝐶}_{𝑖}$= $𝐴$.

• TROVA($𝑥,𝑆)=𝐶$

se $𝑥$ appartiene ad una componente di $𝑆$ allora $𝐶$ è l'identificatore della componente cui $𝑥$ appartiene.

• FONDI($𝑥,𝑦,𝑆)=S^{\prime }$

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