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.
- CREAMFSET (INSIEME)
MFSet
- TROVA (ELEMENTO, MFSET)
componente
- FONDI (ELEMENTO, ELEMENTO, MFSET)
MFSet
- CREAMFSET(
)=![{\displaystyle {\mathit {S))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5b047feeb7dc2e5628923eefa42344135b48a21)
è quindi una famiglia di
= |
| componenti
,...,
ciascuno dei quali contiene un solo elemento di
tale che
=
.
- TROVA(
![{\displaystyle {\mathit {x)),{\mathit {S)))={\mathit {C))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b08d12c12e0ae8a60a21b05bc174408293ce8de)
se
appartiene ad una componente di
allora
è l'identificatore della componente cui
appartiene.
- FONDI(
![{\displaystyle {\mathit {x)),{\mathit {y)),{\mathit {S)))=S'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecf4045131617cf5aec98505ad61c330d52a9222)
se TROVA(
è diverso da
quindi
ed
appartengono a componenti distinte di
allora
è formato da tutte le componenti di
che non contengono
o
, e da una nuova componente data dall'unione delle due componenti contenenti
ed
.